c语言练习题.txt

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

    ┌─┬──┬─┐            ┌──┬──┐
    │  │    │  │ １２２４   │    │    │  １１２２
    │  ├──┤  │            ├──┼──┤
    │  │    │  │ １３３４   │    │    │  ３３４４
    ├─┼──┼─┤            ├──┼──┤
    │  │    │  │ ５６６８   │    │    │  ５５６６
    │  ├──┤  │            ├──┼──┤
    │  │    │  │ ５７７８   │    │    │  ７７８８
    └─┴──┴─┘            └──┴──┘



 24. 某地街道把城市分割成矩形方格，每一方格叫作块，某人从家中出发上班，
 向东要走Ｍ块，向北要走Ｎ块，（见图）。请设计一个程序，由计算机寻找并
 打印出所有的上班的路径。

                                               单位

           ┬   ┌─┬─┬─┬─┬─┬─┬─┐
           │   │  │  │  │  │  │  │  │
           │   ├─┼─┼─┼─┼─┼─┼─┤
           ↓   │  │  │  │  │  │  │  │
           Ｎ   ├─┼─┼─┼─┼─┼─┼─┤
           ↑   │  │  │  │  │  │  │  │
           │   ├─┼─┼─┼─┼─┼─┼─┤
           │   │  │  │  │  │  │  │  │
           ┴   └─┴─┴─┴─┴─┴─┴─┘
           家   ├─────→Ｍ←─────┤





 25. (量水) 用存水为Ｍ，Ｎ升的两个罐子，量出Ａ升水。
 26. (八数码问题) ８个编有数码１￣８的滑牌，能在３＊３的井字格中滑动。
 井字格中有一格是空格，用０表示，因而空格周围的数码滑牌都可能滑到空格中去.

 下图是数码滑牌在井字格中的两种状态：

         ┎─┬─┬─┒                        ┏━┯━┯━┓
         ┃2 │8 │3 ┃                        ┃1 │2 │3 ┃
         ┠─┼─┼─┨                        ┠─┼─┼─┨
         ┃1 │6 │4 ┃     －－－－＞         ┃8 │0 │4 ┃
         ┠─┼─┼─┨                        ┠─┼─┼─┨
         ┃7 │0 │5 ┃                        ┃7 │6 │5 ┃
         ┗━┷━┷━┛                        ┗━┷━┷━┛

            初始状态                              目标状态

 以左图为初始状态，右图为目标状态，请找出从初始状态到目标状态的滑牌移步
 序列，具体要求：

    （１）输入初始状态和目标状态的数据；
       ａ、分别用两行输入上述两项数据：
         例：Enter the initial state:2 8 3 1 6 4 7 0 5
             Enter the final state:1 2 3 8 0 4 7 6 5
       ｂ、对输入数据应有查错和示错功能；
    （２）实现从初始状态到目标状态的转换（如不能实现，程序应输出不能实现
    的提示信息）；
    （３）输出结果，每移动一步都必须在屏幕上显示:
       ａ、移动每一步时的序号，最后一步的序号即为移动总步数；
       ｂ、每一步移动后以３＊３表格形式显示状态。
    （４）要求能使移动步数尽可能少；


 27. 给出一个有８个格子的表格，除３个格子外，每个格子中可放入一个数字，这
 些数字取自自然数 1 到 5，放入格子中的数字不得相同，剩余的３个格子是空格
 （用Ｏ表示）。图１是一个放数字与空格的特例。现要求编程实现从初始表格状态
 变化到目标表格状态。初始状态和目标状态都是可变的（图１，图２所示的状态仅
 是一个特例），由键盘输入格子中的数字（０￣５）。

    移动规则：

   (1) 每一个数字只可以通过虚线移入相邻空格。如图１中，允许“２”左移入空
   格，而不能上移进入上面空格。
   (2) 只允许水平移动或垂直移动，不允许斜移。
   (3) 移动后，该数字原先所在的格子变成空格。

    实现目标：

   (1) 输入初始表格状态和目标表格状态的数据。
     ① 分别在一行内输入上述两项数据；
     ② 对输入的数据应有查错和报错功能；
   (2) 实现从初始状态到目标状态的转换（如不能实现也应给出必要的说明）。
   (3) 显示结果：每移动一步都应在屏幕上有如下信息：
     ① 显示每一步移动的序号。所以最后一步的序号就是移动的总步数。
     ② 显示每一步移动前后的表格状态。
   (4) 以最少的移动步数达到目标。

              ┎─┰─┰─┒                          ┎─┰─┰─┒
              ┃３┃４┃０┃                          ┃０┃０┃０┃
          ┎─╂─╂  ╂─╂─┒                  ┎─╂─╂  ╂─╂─┒
          ┃０  １  ０  ２  ５┃                  ┃１  ２  ３  ４  ５┃
          ┖─┸─┸─┸─┸─┚                  ┖─┸─┸─┸─┸─┚

                图 １０－１                             图 １０－２

                初始状态Ａ                              目标状态Ｂ



 28. ｎ枚银币 C1,C2,...,Cn, 其中有一块不合格,不合格的银币比正常的要重。现用
 一天平找出不合格的一块，要求在最坏的情况下，用的天平次数最少。



 29. 把一段文章按要求排版。文章的输入方式为：由键盘输入一段以回车符结束的文章
 （最大长度 2000 个字符）。排版时以单词为基本单位。单词由不含空格的任意字符组
 成，是长度小于２０个字符的串。空格符是分隔单词的唯一字符，在输入时连续的空格
 符在处理时应先化简为单个空格符。在排版前应先输入，排版后每行的字符数为Ｎ，排
 版后将整理好的文章按行输出。输出时不能将一个完整的单词截断，并要求输出的总行
 数最小。将每个不足Ｎ个字符的行用空格补足，填充空格符的方式有以下三种。

    １）将填充的空格符置于每行的末尾，并要求每行的起始为单词。
    ２）将填充的空格符置于每行的开始，并要求每行的末尾为单词。
    ３）将填充的空格符平均分配在每行中，并保证行的起始和末尾均为单词。



 30. 某机要部门安装了电子锁。Ｍ个工作人员每人发一张磁卡，卡上有开锁的密码特征。

 为了确保安全，规定至少要有Ｎ个人同时使用各自的磁卡才能将锁打开。问电子锁上至
 少要有多少种特征? 每个人的磁卡上至少要有多少特征? 如果特征的编号以小写英文字
 母表示，将每个人的磁卡的特征编号打印出来，要求输出的电子锁的总特征数最少。

    设 3<=M<=7, 1<=N<=4, Ｍ与Ｎ由键盘输入，工作人员编号用 1#,2#,...表示.
 31. 甲乙两人从２４枚棋子中轮流取子，甲先取，规定每次所取的枚数不能多于上
 一个人所取的枚数，也不可不取。

  （１）甲第一次取多少枚才能保证甲取得最后一枚，当然，他也不能第一次就把
 所有棋子都取走。
  （２）讨论棋子总数Ｎ（一定是偶数）从６到３０的各种情况。讨论内容包括：

 对各个Ｎ，是否存在一个小于Ｎ的枚数Ｍ，甲第一次取Ｍ枚后就能保证甲如果策略
 正确,一定能取到最后一枚棋子。


 32. ( 走棋 ) 一个４＊４的方阵如图。有一个小卒从上往下走。走至格子１后就
 不能走动，走至０后，若下方为１，则向左或向右走，下方为０，则向下走。求所
 有走法。

              ┌─┬─┬─┬─┐
              │1 │0 │0 │0 │
              ├─┼─┼─┼─┤
              │0 │0 │1 │0 │
              ├─┼─┼─┼─┤
              │0 │1 │0 │0 │
              ├─┼─┼─┼─┤
              │1 │0 │0 │0 │
              └─┴─┴─┴─┘


 33. ( 野人与传教士 ) 设有三个传教士和三个野人来到河边，打算乘一只船从右
 岸渡到左岸去。该船最大负载能力为两人，在任何时候，如果野人人数超过传教士
 人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过
 河去呢？



 34. ( 取棋子 ) 设有Ｎ颗棋子，由人和计算机轮流从中取走若干颗。每方每次最
 多取Ｋ颗，最少取１颗 (Ｋ值不能超过总数的一半，也不能小于１)。试编写一程
 序使计算机有较多的获胜机会。

    屏幕输入提示:

    (1) 输入竞赛规则：A. 取最后一颗棋子的那一方为败.
                      B. 取最后一颗棋子的那一方为胜.
    (2) 总共有多少颗棋子？
    (3) 一次最多取几颗？
    (4) 谁先取？
    (5) 每个回合都应显示: A. 你取几颗？
                          B. 我取走......颗，还剩......颗.
    (6) 竞赛过程中发生违例时，打印出:  竞赛无法进行下去！
    (7) 竞赛结束后打印：
    I win!（我胜！）或  You win!（你胜！）。

 35. ( Grundy博弈 ) 在两位选手面前放着一堆铜币。第一位选手把原堆分成不相
 等的两堆。然后每个选手轮流地这样做，即当轮到某一方分时, 他把已被分开的任
 一堆再分成不相等的两堆。博弈这样一直进行下去，直到每一堆都只剩下一个或两
 个铜币为止，这时博弈结束。规定首先遇到这种情况的选手为输。
 36. 猴子选大王：
   ① N 只猴子站成一行，每隔 M 只从头到尾报数，反复进行,报过数的退出，打
 印每次退出的猴子的编号,直到剩下一只为止。
   ② N 只猴子站成一行，每 M 只报数。先从头到尾，报到尾后，再返回从尾到头
 报数，打印每次方向及过程，直到剩下二只时，以排到后面的(指报数方向)为大王。
   ③ N 只猴子围成一圈，从第 P 个开始，每隔 M 只报数，打印每次过程，只剩下
 一个时为大王。



 37. 已知 N 个正整数满足 K1+K2+...+Kn=M。求一组最佳的分解，使得
 K1*K2*....*Kn 为最大。
   例如：N=2时，给定 K1+K2=6,当 K1=3,K2=3 时，K1*K2=9 为最大


 38. 有一集合中有 N 个元素，每个元素均为自然数。给定一个 total （假设每个
 元素值均小于total)，求满足条件的所有子集，子集中各元素之和应等于total。

 39. 一个集合满足如下条件：
   (1)１是集合的元素；
   (2) 若 P 是集合的元素，则 2*P+1，4*P+5 也是集合的元素。
 求：此集合中最小的 K 个元素。
 　③ 对ＡＢＣ作全排列而得的六个三位数之和为 2886。



 40. 一个整型变量只能用来存贮较小的 N！的值，当 N 较大时，可将阶乘值中的
 每一个数字放在一个一维数组的一个元素中。使用这方法，打印：
    ① Ｎ！的值；
    ② Ｎ！－Ｍ！（Ｍ＞Ｎ）；
    ③ Ｎ！＋Ｍ！
 41. (合并链表) 已知两个链表 AN={a1,a2,...an}, BN={b1,b2,...bm}, 将其合并
 为一个链表 CN={a1,b1,a2,b2,...}



 42. (算术表达式求值) 输入一个由数字、+，-，*，/ 及括号组成的算术表达式，
 求其值。



 43. 对于次数很高，但项目很少的多项式，可用链表来表示。
  例如：X^1000－76*X^76＋3*X^3－7可表示为

  ┌─┬──┬─┐  ┌──┬─┬─┐   ┌─┬─┬─┐  ┌─┬─┬──┐
  │1 │1000│  ┼→│-76 │78│  ┼→ │3 │3 │  ┼→│-7│0 │ NIL│
  └─┴──┴─┘  └──┴─┴─┘   └─┴─┴─┘  └─┴─┴──┘

 在此方式下，编程完成两个多项式的加法与乘法。



 44. (一元多项式加法) 实现两个整系数一元多项式的加法。例如, 对于多项式
 5*X^6＋4*X^3－7*X^4＋1 与多项式 50*X^2＋4*X, 运算结果为：
 5*X^6－7*X^4＋4*X^3＋50*X^2＋4*X＋1。

   程序要求：键盘输入多项式的各项系数及指数，每项系数及指数为一组数据（系
 数及指数之一可为零），以'0,0'结束一个多项式的输入，结果按降幂排列，同类
 项要合并（指数最大不超过３０）。

   上例第一式的输入为：    5,6
                           4,3
                          -7,4