c语言练习题.txt

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

                           1,0
                           0,0
  输出结果应为：5*x^6-7*x^4+4*x^3+50*x^2+4*x+1.


 45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把
 它们相加， 并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=
 ((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中
 间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:
 (4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.
 若给出 N 个数的数列，求出此数列的最小代价。
 46. 设有一个字符串，长度小于 100，且全部以英文字母组成。对字串中的每个字
 母可用 0,1,2 三个数字进行编码，且数字可以重复使用。
 程序要求：(1) 输入字符串，并能判断输入是否有错；
           (2) 输出对应的编码表及码长，要求字串的编码总长度为最短；
           (3) 根据上述编码表，给出一些编码，然后求出其原字符串。
 例如：输入的字符为:ABCBAAADDEF
     其对应的编码表为：
         A:   2                B:  10
         C:  11                D:  12
         E:  00                F:  O1
 对应的编码为：210111022212120001       总码长为：18
 根据该编码，给出编码:010001121110222   则输出字串:FEFDCBAAAA.

 47. 某些密码由 N 个英文字母组成(N〈26), 每个字母的平均使用率为:W1,W2,...
 ,Wn, 要求编程完成下列任务：
    ① 键入英文字母及个数；
    ② 键入Ｎ个英文字母的使用频率；
    ③ 用二进制数对该Ｎ个英文字母进行编码（最短，无二义性）；
    ④ 键入字母短文（单词用空格区分），输出相应编码；
    ⑤ 键入二进制编码短文，输出译文。

 48. 将４个红球，３个白球与３个黄球排成一排，共有多少种排法？

 49. 有面值为 M..N 的邮票各一枚，共能拼出多少不同的面额。

 50. 有一个四阶方阵，随机产生 1..16 这 16 个自然数（不重复），依次填入每
 个方格中。要求用最少的对调次数，使每一行、每一列以及对角线上的四个数之和
 均相等。打印每一次对调的过程。

 51. 微型蓝球赛. 甲,乙两队进行蓝球比赛,结果甲队以S:T 获胜.(T<S<=10, S,T
 由键盘输入). 比赛中, 甲队得分始终领先(严格大于乙队). 规定以任何方式进一
 球都只得一分. 编程序打印该比赛的每一种可能的不同的得分过程, 以及所有不同
 过程的总数.

 52. 求两整型数组错位相加的最大面积.
    设整型数组 C 具有 N 个分量: C=(C1,C2,...,CN), 两相连分量(C[I],C[I+1])
 可计算一个面积: 若C[I],C[I+1]同号, 则面积 SI=abs(C[I]+C[I+1])/2, 否则,面
 积等于 (abs(a*C[I])+abs(b*C[I+1]))/2, 其中, a>0,b>0,a+b=1 (详见下图),数
 组 C 的面积 A=S[1]+S[2]+...+S[N-1].
     编程要求如下:
  从键盘输入 N, 再输入两个具有 N 个分量的数组: A1,A2:ARRAY [1..N] OF
 INTEGER; 将 A1,A2 错位相加(详见后面的例子)得数组A3, 求 A3 的面积.编程给
 出一个错位相加的方案, 使 A3 的面积最大.
    例: 设 N=3, A1=(3,7,2), A2=(-5,7,-4), 则应考虑 9 种情况:
                    (1)                         (2)
        A1  3  7  2                       3  7  2
        A2              -5  7  -4                  -5  7  -4
        A3  3  7  2  0  -5  7  -4         3  7  2  -5  7  -4
                    (3)                         (9)
        A1  3  7  2                                     3  7  2
        A2       -5  7 -4       ......     -5  7  -4
        A3  3  7 -3  7 -4                  -5  7  -4  0 3  7  2

 53. (工作安排问题) 现有 N (N≤8) 件工作, 分别由 N 个人完成, 每人都完成一
 件,且只完成一件, 每人完成不同工作的时间不同. 试设计一种分配工作方案, 使
 完成 N 件工作所需的总时间最少.
    原始数据由文本文件 EXAM1.TXT 给出, 其格式如下:
    第 1 行:        工作任务数(N)
    第 2 -- N+1 行: 第 i+1 行为第 i 个人完成各件工作所需的时间. 以上各数
 均为不超过 1000 的正整数.
    计算结果可直接在屏幕上输出: 第一行为工作分配方案, 共 N 组, 每组数据的
 形式为 a-b, 其中 a 为工作人员编号, b 为他应完成的工作序号.
    例: 设 EXAM1.TXT 的数据为:
         4
         2  15  13  4
         10  4  14  15
         9  14  16  13
         7  8  11  9
     对此, 一个正确的输出可以是
         1-4, 2-2, 3-1, 4-3
         TOTAL=28

 54. 求Ｎ个字符串的最长公共子串，Ｎ＜＝２０，字符串长度不超过２５５。
    例如：Ｎ＝３，由键盘依次输入三个字符串为
      What is local bus ?
      Name some local buses.
      local bus is a high speed I/O bus close to the processer.
 则最长公共子串为"local bus"。
 ( 参看程序 9 )

 55. (液晶显示) 下图是用液晶七笔阿拉数字表示的十个数字，我们把横和竖的一
 个短划都称为一笔，即７有３笔，８有７笔等。请把这十个数字重新排列，要做到
 两相邻数字都可以由另一个数字加上几笔或减去几笔组成，但不能又加又减。比如
 ７→３是允许的，７→２不允许。编程打印出所有可能的排列。
    如：４１０７３９５６８２。

 56. (Ｎ阶梵塔) 有Ｋ根棒，第一根上放Ｎ片大小不等的圆盘，并保持上小下大的
 顺序。现将Ｎ片圆盘从第１根移至第Ｋ根，移动中均保持上小下大的顺序，问最少
 移几次方得结果，求出移动方案。
 57. 某一印刷厂有六项加工任务，对印刷车间和装订车间所需时间见下表（时间单
 位：天）
            任务  │Ｊ1  Ｊ2  Ｊ3  Ｊ4  Ｊ5  Ｊ6
        ─────┼───────────────
          印刷车间│ ３  １２  ５   ２   ９  １１
          装订车间│ ８  １０  ９   ６   ３  １
 如何安排加工顺序，使加工时间最少。

 58. 将７万元投资到Ａ，Ｂ，Ｃ三项目上，其利润见下表：
        投资额(万元)│ １    ２    ３    ４    ５    ６    ７
        ──────┼────────────────────
            项  Ａ  │0.11  0.13  0.15  0.24  0.24  0.30  0.35
                Ｂ  │0.12  0.16  0.21  0.25  0.25  0.29  0.34
            目  Ｃ  │0.08  0.12  0.20  0.26  0.26  0.30  0.35
  如何分配投资额，使获得的利润最大。

 59. 无根树与通常所说的树（有根树）很相似，它包含有节点和枝，但不含有根。
 无根树节点之间只有相邻关系。如图一所示，是一棵有七个节点的无根树，以图一
 的Ａ为根节点得到图二所示的有根树，以Ｂ为根节点得到图三所示的有根树，但从
 无根树的角度看，图一、二、三是结构相同的无根树，同时无根树的结构与节点的
 名称无关。
    有根树可以用字符串的形式表示，其递归表示方法是：
        根节点（子树１    子树２    子树３...）
 图一，图二的有根树可表示为 A(B(CF(EGD))) 和 B(ACF(EGD))。由于子树的表示
 顺序可以不同，所以一棵有根树可以有多种表示方法，如图三又可表示成
 B(F(EGD)CA) 或 B(ACF(DE(G)) 等。表示无根树时，可以以它任一节点为根节点，
 将其看作有根树，从而可以利用有根树的字符串表示形式来表示无根树。
    任务一：由键盘读入一个字符串表示的无根树，无根树的各节点的名称用互不
 相同的大写英文字母表示。由用户输入一个节点的名称，程序应能够输出一种以该
 节点为根节点的字符串形式。程序输出无根树的字符串形式时，各个节点的名称无
 关紧要，所有节点都以Ｐ表示，以后的各种输出也采用这种形式。例如：输入无根
 树的字符串形式：Ａ（Ｂ（ＣＤ（ＥＦ））），指定根节点为Ｄ，程序应能输出
 Ｐ（Ｐ（ＰＰ）ＰＰ），Ｐ（ＰＰ（ＰＰ）Ｐ），Ｐ（ＰＰＰ（ＰＰ））中的任意
 一种即可。
    任务二：输入两个串表示的无根树，判断其结构是否一样。注意它与节点名称
 无关，只考虑结构。
    任务三：输入无根树的总枝数Ｎ（1<=N<=11），输出所有枝数为Ｎ的互不相同
 的无根树，并记录总数。以字符串形式输出，例如：N=5 时共有６种不同结构的无
 根树。
    注意：各种树结构的字符串表达形式不唯一。

 60. 用Ｎ＊Ｎ（１＜＝Ｎ＜＝８）的格点阵代表海，其中＊号代表岛。给你一组编
 码信息，让你重构一张地图。这组信息是按垂直方向，水平方向岛的情况摘取的。
 下例中，每行右边的数字按顺序表示该行中“岛组”的大小，如第一行数字为
 “１２”，表示该行第一“岛组”由一个岛组成，第二“岛组”由两个岛组成，而
 第四列下面的“２３”则表示本列由两个“岛组”组成，第一个“岛组”由两个岛
 组成，第二个“岛组”由三个岛组成。
    任务：编程执行以下步骤，直到给定的输入 (ASCII) 文件中的信息组全部读完
 为止，步骤如下：
   （１）从输入文件 (ASCII 文件）中读入下一个信息块，并将它显示在屏幕上。
 每个信息块组成为：
    格点阵大小 (N)，以后是行的约束条件（Ｎ行的），列的约束条件（Ｎ列的）,
 每行（或每列）的约束条件是
    一行数字，数字间有空格，最后用０结束。上面的例子如图所示。
   （２）重构这张地图（若有多个解，要逐个构成地图），并显示。
   （３）将重构的地图以ＡＳＣＩＩ文件形式输出。每岛以＊后加一个空格表示；
 空白处用连续的两个空格表示。若同一已知条件可画出多张地图，相互间用空行隔
 开；若一组已知条件画不出地图，用“ＮＯ  ＭＡＰ（占一行）表示。由不同的信
 息组求得的解用“ＮＥＸＴ  ＰＲＯＢＬＥＭ”（占一行表示）１＜＝Ｎ＜＝８.

 61. 一个餐厅在相继的Ｎ天里，第 i 天需要 Ri 块餐巾(i=1，2，...，N)。餐厅
 可以从三种途径得到餐巾:
   (1) 购买新的餐巾，每块需Ｐ分；
   (2) 把用过的餐巾送到快洗部，洗一块需Ｍ天，费用需Ｆ分(Ｆ＜Ｐ)；
   (3) 把餐巾送到慢洗部，洗一块需Ｎ天(Ｎ＞Ｍ)，费用需Ｓ分(Ｓ＜Ｆ)。
 在每天结束时，餐厅必须决定将多少块用过的餐巾送到快洗部，多少块送慢洗部，
 多少块保存起来延期送洗。在每天开始时，餐厅必须决定是否购买新餐巾及购买多
 少，使洗好的和新购的餐巾之和满足当天的需求量Ri，并使Ｎ天总的费用最小。请
 编程输入总天数，每天所需的餐巾块数以及每块餐巾的新购费用Ｐ，快，慢洗费用
 Ｆ，Ｓ，和所需天数Ｍ，Ｎ，输出每天开始时需购新餐巾数，结束时送快，慢洗部
 和延期送洗的餐巾数。

 62. ( 旅行商 ) 一个推销员计划做一次旅行，他必须访问如图所示每个城市。每
 两个城市的路径旁标有路径。要求从城市Ａ出发，访问每个城市一次，且只访问一
 次，最后返回城市Ａ，求一条距离最短的路线。

 63. (tic__tac__toe 游戏) tic__tac__toe 游戏的规则是：从一个空的 (N*N) 的
 棋盘（例如Ｎ＝３）开始，甲乙二人轮流将棋子放置在棋盘上未被占据的方格中，
 例如甲第一个放，他把棋子放在中央的方格里， 然后轮到乙放，他把棋子放在第
 一行中间的方格里。于是又轮到甲放，......如此进行下去。判定胜负的方法是：
 若某一游戏者有Ｎ枚棋子占据了一横行，或一竖列，或一对角线，则此人获胜；若
 直至整个棋盘被占满还没有一方获胜，则为平局。
     ┏━┯━┯━┓         ┏━┯━┯━┓         ┏━┯━┯━┓
     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │Ｏ│  ┃
     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨
     ┃  │  │  ┃         ┃  │Ｘ│  ┃         ┃  │Ｘ│  ┃
     ┠─┼─┼─┨         ┠─┼─┼─┨         ┠─┼─┼─┨
     ┃  │  │  ┃         ┃  │  │  ┃         ┃  │  │  ┃
     ┗━┷━┷━┛         ┗━┷━┷━┛         ┗━┷━┷━┛
 64.  以字符串形式由键盘输入两个高精度的８进制正整数，串长小于２５５，以
 第一个数为被除数，第二个数为除数，进行高精度除法运算，并显示按 8 进制表
 示的商和余数。
 ( 参看程序 8 )

 65. ( NOI'94.1_1 ) 键盘输入一个仅由小写字母组成的字符串，输出以该串中任
 取Ｍ个字母的所有排列及排列总数。

 66. ( NOI'94.1_2 ) 编程实现两个高精度实数减法，两数分别由键盘输入，均不
  超过２４０位。
 ( 参看程序 5 )

 67. ( NOI'94.1_3 ) 一个实数数列共有Ｎ项，已知a(i)=(a(i-1)-a(i+1))/2+d，
（１〈i〈Ｎ）(N<60) , 键盘输入Ｎ，d，a(1)，a(n)，m，输出 a(m)。

 68. ( NOI'94.1_4 ) 键盘输入一个高精度的正整数Ｎ，去掉其中任意Ｓ个数字后
 剩下的数字按原左右次序将组成一个新的正整数。编程对给定的Ｎ和Ｓ，寻找一种
 方案使得剩下的数字组成的新数最小。输出应包括所去掉的数字的位置和组成的新
 的正整数。（Ｎ不超过２４０位）

 69. 在两个文本文件中各存有一个以西文制表符制成的未填入任何表项的表结构，
 分别称之为表１和表２，要求编程将表１和表２下述规则合并成表３：
     规则：表１在表２之上，表１和表２的左边框对齐，将表１的最低行与表２的
 最顶行合并。例：在你的Ｃ盘根目录下有两个文件 t0.1 和 t0.2，分别存放上述
 的表１和表２，经上述规则合并后得到表３，放在文件中。三张表见下图：
  ┎─┰─┰─┰─┒                                ┎─┰─┰─┰─┒
  ┃  ┃  ┃  ┃  ┃        ┎┰─┰─┒            ┃  ┃  ┃  ┃  ┃
  ┠─╂─╂─╂─┨        ┃┃  ┃  ┃            ┠─╂─╂─╂─┨
  ┃  ┃  ┃  ┃  ┃        ┖┸─┸─┚            ┃  ┃  ┃  ┃  ┃
  ┖─┸─┸─┸─┚                                ┠┰┸┰┸┰┸─┚
                                                    ┃┃  ┃  ┃
                                                    ┖┸─┸─┚
        表１                    表２                     表３
    编程要求：
   (1) 程序应能自给定的文件中读入两个源表并显示。
   (2) 若源表有错，应能指出其错。
   (3) 将表１和表２规则合并成表３，并显示之。
   (4) 所有制表符的ＡＳＣＩＩ码应由选手自己从给出的示例文件中截取。

 70. (圆盘问题) 从左向右依次安放 4 根细柱 A,B,C,D. 在 A 上套有 N (N≤20)
 个直径相同的圆盘, 从下到上依次用连续的小写字母 a,b,c,...编号, 将这些圆盘
 经过 B, C 单向地移入 D (即不允许从右向左移动). 圆盘可在 B,C 中暂存. 从键
 盘输入 N, 及前 N 个小写字母的一个排列, 它表示最后在 D 盘上形成的一个从下
 到上的圆盘序列. 请用文本文件 ANS2.TXT 输出形成这一排列的操作过程.
   该文件的每一行为一个形如 "k M L" 的字母序列, 其中 k 为圆盘编号, M 为 k
 盘原先的柱号, L 为新柱号. 或者直接在屏幕上输出"No",表示不能生成这种排列.
     例:                                ┃      ┃      ┃      ┃
     键盘输入:                          ┃      ┃      ┃      ┃
         3                        d   ━╋━    ┃      ┃      ┃
         acb                      c   ━╋━    ┃      ┃      ┃
     则一个正确的输出文件         b   ━╋━    ┃      ┃      ┃
  可以是:                         a   ━╋━    ┃      ┃      ┃
      c  A  B                       ━━┻━━━┻━━━┻━━━┻━