蓝桥杯培训教程

更新时间：2024-04-20 01:32:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

蓝桥杯培训怎么样推荐度：
相关推荐

蓝桥杯培训教程

一、逻辑推理 ................................................................................................................................... 2 二、排序........................................................................................................................................... 8 三、图形(矩阵) .............................................................................................................................. 12 四、数字变幻 ................................................................................................................................. 21 五、数字组合与拆解 ..................................................................................................................... 26 六、字符串..................................................................................................................................... 45 七、数制转换 ................................................................................................................................. 50 八、排列组合 ................................................................................................................................. 55 九、其它......................................................................................................................................... 55 十、数据结构 ................................................................................................................................. 72

一、逻辑推理

1、谁是窃贼：

公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎。在回答公安人员的问题中：甲说：―乙没有偷，是丁偷的。‖ 乙说：―我没有偷，是丙偷的。‖ 丙说：―甲没有偷，是乙偷的。‖ 丁说：―我没有偷‖

请根据这四人的谈话判断谁是盗窃者

*问题分析与算法设计

假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贼。

由题目已知：四人中仅有一名是窃贼，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话：―X没偷，X偷了‖，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式：

甲说：‖乙没有偷，是丁偷的。‖ B+D=1 乙说：―我没有偷，是丙偷有。‖ B+C=1 丙说：―甲没有偷，是乙偷的。‖ A+B=1 丁说：―我没有偷。‖ A+B+C+D=1

其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贼的条件。

#include void main() {

int i,j,a[4];

for(i=0;i<4;i++) /*假定只有第i个人为窃贼*/ {

for(j=0;j<4;j++) /*将第i个人设置为1表示窃贼，其余为0*/

if(j==i)

a[j]=1; else

a[j]=0;

if(a[3]+a[1]==1&&a[1]+a[2]==1&&a[0]+a[1]==1) /*判断条件是否成立*/ {

printf(\成立*/

for(j=0;j<=3;j++) /*输出计算结果*/ if(a[j]) printf(\printf(\}

}

2、谁说假话：

张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。现在问：这三人中到底谁说的是真话，谁说的是假话？

*问题分析与算法设计

分析题目，每个人都有可能说的是真话，也有可能说的是假话，这样就需要对每个人所说的话进行分别判断。假设三个人所说的话的真假用变量A、B、C表示，等于1表示该人说的是真话；表示这个人说的是假话。由题目可以得到： *张三说李四在说谎张三说的是真话：a==1&&b==0 或张三说的是假话：a==0&&b==1

*李四说王五在说谎李四说的是真话：b==1&&c==0 或李四说的是假话：b==0&&c==1

*王五说张三和李四都在说谎王五说的是真话：c==1&&a+b==0 或王五说的是假话：c==0&&a+b!=0

上述三个条件之间是―与‖的关系。将表达式进行整理就可得到C语言的表达式： (a&&!b||!a&&b)&&(b&&!c||!b&&c)&&(c&&a+b==0||!c&&a+b!=0) 穷举每个人说真话或说假话的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为―真‖的情况就是正确的结果。 *程序说明与注释 #include int main() {

int a,b,c;

for(a=0;a<=1;a++) for(b=0;b<=1;b++) for(c=0;c<=1;c++)

if((a&&!b||!a&&b)&&(b&&!c||!b&&c)&&(c&&a+b==0||!c&&a+b!=0)) {

printf(\printf(\printf(\}

}

*运行结果

Zhangsan told a lie (张三说假话) Lisi told a truch. (李四说真话) Wangwu told a lie. (王五说假话)

3、诚实族和说谎族：

诚实族和说谎族是来自两个荒岛的不同民族，诚实族的人永远说真话，而说谎族的人永远说假话。迷语博士是个聪明的人，他要来判断所遇到的人是来自哪个民族的。迷语博士遇到三个人，知道他们可能是来自诚实族或说谎族的。为了调查这三个人是什么族的，博士分别问了他们的问题，这是他们的对话：

问第一个人：―你们是什么族？‖，答：―我们之中有两个来自诚实族。‖第二个人说：―不要胡说，我们三个人中只有一个是诚实族的。‖第三个人听了第二个人的话后说：―对，就是只有一个诚实族的。‖

请根据他的回答判断他们分别是哪个族的。

*问题分析与算法设计

假设这三个人分别为A、B、C，若说谎其值为0，若诚实，其值为1。根据题目中三个人的话可分别列出：

第一个人： a&&a+b+c==2||!a&&a+b+c!=2 第二个人： b&&a+b+c==1||!b&&a+b+c!=1 第三个人： c&&a+b+c==1||!c&&a+b+c!=1 利用穷举法，可以很容易地推出结果。

*程序说明与注释 #include int main() {

int a,b,c;

for(a=0;a<=1;a++) /*穷举每个人是说谎还是诚实的全部情况*/ for(b=0;b<=1;b++) /*说谎：0 诚实：1*/ for(c=0;c<=1;c++)

if((a&&a+b+c==2||!a&&a+b+c!=2) /*判断是否满足题意*/ &&(b&&a+b+c==1||!b&&a+b+c!=1) &&(c&&a+b+c==1||!c&&a+b+c!=1)) {

printf(\输出判断结果*/ printf(\printf(\}

}

*运行结果

A is a lier (说谎族) B is a lier (说谎族) C is a lier (说谎族)

4、球队进行比赛

两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。已抽签决定比赛

名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单

*程序说明与注释

#include #include main() { char i,j,k; /*i是a的对手，j是b的对手，k是c的对手*/ for(i='x';i<='z';i++) for(j='x';j<='z';j++) { if(i!=j) for(k='x';k<='z';k++) { if(i!=k&&j!=k) { if(i!='x'&&k!='x'&&k!='z') printf(\ } } } getch(); }

5、谁考了100分

已知4位同学中的一位数学考了100分，当小李询问这4位是谁考了100分时，4个人的回答如下：

A说：不是我。 B说：是C C说:是D。 D说：他胡说。

已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出考100分的人。 #include void main() { char thisman=' '; int k,n=0; for(k=1;k<=4;k++) { thisman=64+k; n=(thisman!='A')+ (thisman=='C')+ (thisman=='D')+ (thisman!='D');

}

if(n==3) { printf(\得100分的是%c\\n\ break; } }

if(k>4) printf(\无解!\\n\

6、新郎新娘问题：

教堂中来了A B C三个新郎和X Y Z三个新娘，问新人中的三位，他们互相与谁结婚。下面是三个人的回答，但全是假话，判断他们谁与谁结婚 A说他与X结婚 X说她与C结婚 C说他与Z结婚 #include void main() { int a,b,c,n; char x[3]={'X','Y','Z'}; for(a=0;a<3;a++) for(b=0;b<3;b++) if(a!=b) { c=3-a-b; n=(a==0)+(c==0)+(c==2); if(n==0) printf(\ } }

7、寻找肇事车辆：

一辆汽车撞人后逃跑,4个目击者提供如下线索: 甲说:牌照第三,第四位相同(从左边数起). 乙说:牌号为31xxxx.

丙说:牌照第五,第六位相同(从左边数起).

丁说:第三位~第六位是一个整数的平方.求出此牌照号码 #include #include void main() { int i,j,k,c; for(i=0;i<=9;i++)

for(j=0;j<=9;j++) // if(i!=j) //如果确定三、四位与五六位不同，则用这个语句 { k=i*1000+i*100+j*10+j; for(c=0;c

8、.借书方案知多少小明有五本新书，要借给A，B，C三位小朋友，若每人每次只能借一本，则可以有多少种不同的借法？

*问题分析与算法设计

本问题实际上是一个排列问题，即求从5个中取3个进行排列的方法的总数。首先对五本书从1至5进行编号，然后使用穷举的方法。假设三个人分别借这五本书中的一本，当三个人所借的书的编号都不相同时，就是满足题意的一种借阅方法。 *程序说明与注释 #include int main() {

int a,b,c,count=0;

printf(\for(a=1;a<=5;a++) /*穷举第一个人借5本书中的1本的全部情况*/ for(b=1;b<=5;b++) /*穷举第二个人借5本书中的一本的全部情况*/

for(c=1;a!=b&&c<=5;c++) /*当前两个人借不同的书时，穷举第三个人借5本书中的1本的全部情况*/

if(c!=a&&c!=b) /*判断第三人与前两个人借的书是否不同*/

printf(count%8?\/*打印可能的借阅方法*/ }

*运行结果

There are diffrent methods for XM to distribute books to 3 readers: 1: 1,2,3 2: 1,2,4 3: 1,2,5 4: 1,3,2 5: 1,3,4 6: 1,3,5 7: 1,4,2 8: 1,4,3 9: 1,4,5 10:1,5,2 11:1,5,3 12:1,5,4 13:2,1,3 14:2,1,4 15:2,1,5 16:2,3,1 17:2,3,4 18:2,3,5 19:2,4,1 20:2,4,3 21:2,4,5 22:2,5,1 23:2,5,3 24:2,5,4 25:3,1,2

26:3,1,4 27:3,1,5 28:3,2,1 29:3,2,4 30:3,2,5 31:3,4,1 32:3,4,2 33:3,4,5 34:3,5,1 35:3,5,2 36:3,5,4 37:4,1,2 38:4,1,3 39:4,1,5 40:4,2,1 41:4,2,3 42:4,2,5 43:4,3,1 44:4,3,2 45:4,3,5 46:4,5,1 47:4,5,2 48:4,5,3 49:5,1,2 50:5,1,3 51:5,1,4 52:5,2,1 53:5,2,3 54:5,2,4 55:5,3,1 56:5,3,2 57:5,3,4 58:5,4,1 59:5,4,2 60:5,4,3

二、排序

1、在选美大奖赛的半决胜赛现场，有一批选手参加比赛，比赛的规则是最后得分越高，名次越低。当半决决赛结束时，要在现场按照选手的出场顺序宣布最后得分和最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不用考虑同名次的选手人数。例如：选手序号： 1，2，3，4，5，6，7 选手得分： 5，3，4，7，3，5，6

则输出名次为： 3，1，2，5，1，3，4

请编程帮助大奖赛组委会完成半决赛的评分和排名工作。

*问题分析与算法设计

问题用程序设计语言加以表达的话，即为：将数组A中的整数从小到大进行连续编号，要求不改变数组中元素的顺序，且相同的整数要具有相同的编号。

普通的排序方法均要改变数组元素原来的顺序，显然不能满足要求。为此，引入一个专门存放名次的数组，再采用通常的算法：在尚未排出名次的元素中找出最小值，并对具有相同值的元素进行处理，重复这一过程，直到全部元素排好为止。

*程序说明与注释 #include

#define NUM 7 /*定义要处理的人数*/

int a[NUM+1]={0,5,3,4,7,3,5,6}; /*为简单直接定义选手的分数*/

int m[NUM+1],l[NUM+1]; /*m:已编名次的标记数组 l:记录同名次元素的下标*/ int main() {

int i,smallest,num,k,j; num=1; /*名次*/

for(i=1;i<=NUM;i++) /*控制扫描整个数组，每次处理一个名次*/ if(m[i]==0) /*若尚未进行名次处理(即找到第一个尚未处理的元素)*/ {

smallest=a[i]; /*取第一个未处理的元素作为当前的最小值*/ k=1; /*数组l的下标，同名次的人数*/

l[k]=i; /*记录分值为smallest的同名次元素的下标*/

for(j=i+1;j<=NUM;j++) /*从下一个元素开始对余下的元素进行处理*/ if(m[j]==0) /*若为尚未进行处理的元素*/ if(a[j]

{

smallest=a[j]; /*则重新设置当覵最小值*/ k=0; /*重新设置同名次人数*/

l[++k]=j; /*重新记录同名次元素下标*/ }

else if(a[j]==smallest) /*若与当前最低分相同*/ l[++k]=j; /*记录同名次的元素下标*/

for(j=1;j<=k;j++) /*对同名次的元素进行名次处理*/ m[l[j>=num;

num++; /*名次加1*/

i=0; /*控制重新开始，找下一个没排名次的元素*/ }

printf(\for(j=1;j<=NUM;j++) /*控制输出*/ printf(\}

*运行结果

Player-No Score Rank 1 5 3 2 3 1 3 4 2 5 7 5 5 3 1 3 5 3 7 6 4

*思考题

若将原题中的“名次连续编号，不用考虑同名次的选手人数”，改为”根据同名次的选手人数对选手的名次进行编号“，那么应该怎样修改程序。

2、合并字符串

输入两个已经按从小到大顺序排列好的字符串，编写一个合并两个字符串的函数，使合并后的字符串，仍然是从小到大排列。

输入：两个已经排好顺序（升序）的两个字符串输出：一个合并在一起的有序（升序）的字符串要求：

设计一个效率尽量高的算法，对每个字符串只扫描一遍就可以了。如果采用先进行串连接，然后再进行排序的算法，则效率太低了。程序实例1：

#include #include int main()

{ char a[100],b[100],c[200];

int i=0,j=0,k=0; gets(a);gets(b);

while(i

c[k++]=a[i++]; } else {

c[k++]=b[j++]; } }

//把剩下的字符串合并 while(i

while(j

c[k]='\\0'; //加上结束符 printf(\ return 0; }

输入： abcdef bcefghi

输出：abbccdeeffghi

3、合并果子

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

输入：

输入包括两行，第一行是一个整数n(1<＝n<=10000)，表示果子的种类数。第二行

包含n个整数，用空格分隔，第i个整数ai(1<＝ai<=10000)是第i种果子的数目。

输出：

输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于231。程序实例1：

#include int in[ 100 ];

int find( int len ) //返回最小堆堆序号 {

int i,min=10000,j;

for ( i = 1; i <= len; i ++ ) { if ( in[ i ] < min ) { j = i;

min = in[ i ]; } }

return j; }

int main( void) {

int i,j,min,result,n,a,b; scanf( \

for( i = 1; i <= n; i ++ ) { scanf( \ }

result = 0;

for( i = 1; i <= n - 1; i ++ ) { j = find( n ); //最小的堆 a = in[ j ];

in[ j ] = 10001; j = find( n );

b = in[ j ]; //次最小的堆 in[ j ] = a + b; //合并 result += in[ j ]; }

printf( \ return 0; }

输入： 3 1 2 9 输出：15

三、图形(矩阵)

1、编写函数void rotate(int (*t)[N], int n)。函数功能是将t指向的数组中存储的n×n.矩阵最外圈全部元素做顺时钟旋转900变换。例如：若n=3有如下矩阵： 1 2 3 4 5 6 7 8 9

将矩阵最外圈全部元素做顺时钟旋转900变换后应为： 7 4 1 8 5 2 9 6 3

2、求一个3行5列的二维数组中元素的最大值。 #include typedef unsigned int UINT; int main() {

UINT mx=0,my=0;

UINT juzhen[3][5]={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15}}; UINT maxnumber=0; maxnumber=juzhen[0][0]; for (int i=0;i!=3;++i) {

for (int j=0;j!=5;++j) {

if (juzhen[i][j]>maxnumber) {

maxnumber=juzhen[i][j]; mx=i; my=j; } } }

cout<<\矩阵中最大数是\它所在的位置是\行\列\

//这里的样例输出最大数是15,在2行4列.听起来似乎比三行5列都少一. //这其实是计算机计数都是从0开始.我们人习惯从1开始计数..

//如果你需要从1计数.也很简单..把for循环改改.int i=1;i!=6;++i 里面的循环液照样改下.

return 0; }

3、((2012年预赛题))转方阵

对一个方阵转置，就是把原来的行号变列号，原来的列号变行号例如，如下的方阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 转置后变为： 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16

但，如果是对该方阵顺时针旋转（不是转置），却是如下结果： 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4

下面的代码实现的功能就是要把一个方阵顺时针旋转。 #include #include void rotate(int* x, int rank) {

int* y = (int*)malloc( ); // 填空 sizeof(int)*rank*rank for(int i=0; i

y[_________________________] = x[i]; // 填空 i%rank*rank+i/rank }

for(i=0; i

int main(int argc, char* argv[]) {

int x[4][4] = {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; int rank = 4;

rotate(&x[0][0], rank); for(int i=0; i

for(int j=0; j

printf(\ }

printf(\ } return 0; }

请分析代码逻辑，并推测划线处的代码。

4、(2011年预赛题)由键盘输入一个自然数Ｎ（1≤N≤9），要求程序在屏幕上输出如下图形。

Ｎ＝１时：Ｎ＝３时：Ｎ＝４时：

１１１１１１１１１１１１１１２２２１１２２２２２１１２３２１１２３３３２１１２２２１１２３４３２１１１１１１１２３３３２１１２２２２２１１１１１１１１注：应保证Ｎ在图形中只出现一次，且在中心。

import java.util.Scanner;

import java.text.DecimalFormat; public class LuoxuanJuzhen {

private int[][] array; private int m,n;

public LuoxuanJuzhen(int m, int n) //相当于动态数组，数组的行、列由参数m和n确定 {

this.m = m; this.n = n;

array = new int[m][]; for(int i = 0; i < m; i++) array[i] = new int[n]; }

private void fill() //构造矩阵,填入内容 {

int count = m * n; int direct = 0; int round = 1;

for(int index = 1, x = 0, y = 0; index <= count; index++) {

array[x][y] = index; switch(direct) {

case 0: //向右

if(y < n - round) y++; else {

direct = 1; x++; }

break; case 1://向下

if(x < m - round) x++; else {

direct = 2; y--; }

break; case 2://向左

if(y >= round) y--; else {

direct = 3; x--; }

break; case 3://向上 if(x > round)

x--; else {

direct = 0; round++; y++; }

break; } } }

private void printJuzheng() //输出矩阵 {

//DecimalFormat df = new DecimalFormat(\格式化，让不足三位的数前面用0补足三位，如2表示为002 for(int i = 0; i < m; i++) {

for(int j = 0; j < n; j++) System.out.print(\

//System.out.print(df.format(array[i][j])); System.out.println(); } }

public static void main(String[] args) { Scanner input = new Scanner(System.in); int m = input.nextInt(); LuoxuanJuzhen Juzheng = new LuoxuanJuzhen(m,m); Juzheng.fill();

Juzheng.printJuzheng(); } }

5、空心的倒三角型

背景：请根据要求打印可空心倒三角形。输入：

输入三角形的高度（h >= 0）。输出：

打印相应的空心倒三角形。图样参见测试用例。如：

输入为5，则输出：

*********

* * * * * * * 程序实例1：

#include void main( ) {

int n,i,j;

scanf(\ for(i=0;i

{for(j=0;j<(2*n-1-i);j++)

{if (i==0||i==j||j==(-i+2*n-2))printf(\ else printf(\ }

printf(\ } }

程序实例2：

#include void main() { int r,l,h; scanf(\ for(r=1;r<=2*h-1;r++) printf(\ for(r=2;r<=h;r++) { printf(\ for(l=1;l<=2*h-r;l++) printf(\ } }

6、在20×20的网格中同一直线上四个数的最大乘积是多少？

在以下这个2020的网格中，四个处于同一对角线上的相邻数字用红色标了出来：这四个数字的乘积是：26 63 78 14 = 1788696.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

在这个2020网格中，处于任何方向上（上，下，左，右或者对角线）的四个相邻数字的乘积的最大值是多少？

7、扫雷背景

你玩儿过扫雷游戏吧？有个操作系统中带了这个小游戏，那个系统叫什么来着？在游戏中要想过关，就必须要在一个 NxM 的区域上找出所有的地雷。游戏过程中，计算机会在地图上显示一些数字从而帮助你确定哪里有地雷。例如，在下面这个有两颗地雷的 4x4 的地图（*表示地雷）：

*........*...... 根据上面的地图，可以计算出应该提供给游戏者的数字如下所示：

*10022101*101110 每个数字表示了该方格周围到底有几个地雷，当然，一个方格周围最多的时候只会有八个。输入：

输入中将包括一系列的地图，每个地图的第一行有两个整数 n 和 m（0

针对每一个地图，首先输出一行：

Field #x:其中 x 是当前地图的编号（从 1 开始）。下面的 n 行则将地图中的 \以数字表示，该数字表示该方格周围有多少颗地雷。程序实例1：

#include \ void main()

{ int m,n,t,p,q,x,y,a[200][200]; char c;

t=1; scanf(\

A: if(m==0) goto B;

for(p=0;p<=m;p++) for(q=0;q<=n;q++) a[p][q]=0; for(p=0;p

{a[p][q]=-1;

for(x=p-1;x<=p+1;x++) for(y=q-1;y<=q+1;y++)

if(x>=0&&x<=m&&y>=0&&y<=n&&a[x][y]!=-1) a[x][y]++; } }

printf(\ for(p=0;p

{for(q=1;q<=n;q++) (a[p][q]==-1)?printf(\ printf(\ }

scanf(\ t++;

if(m!=0) {printf(\ B: ; } 输入： 4 4 *... .... .*.. .... 3 5 **... ..... .*... 0 0 输出： Field #1: *100 2210 1*10 1110

Field #2: **100 33200 1*100

程序实例2：

#include int main(void)

{ int f(int m,int n,int i,int j,char a[100][100]); int m,n,i,j,b=0; char a[100][100];

scanf(\ while(m!=0&&n!=0) { b++;

if(b!=1) printf(\ for(i=0;i

for(i=0;i

{ if(a[i][j]=='.') a[i][j]=f(m,n,i,j,a)+48; } }

printf(\ for(i=0;i

{ for(j=0;j

printf(\ }

scanf(\ }

return 0; }

int f(int m,int n,int i,int j,char a[100][100]) { int k,l,b=0;

for(k=i-1;k<=i+1;k++) { for(l=j-1;l<=j+1;l++)

{ if(k<0||l<0||k>=m||l>=n||k==i&&l==j) continue; else if(a[k][l]=='*') b++; } }

return b; } 输入： 3 3 ... ...

... 3 3 *** *** *** 0 0 输出： Field #1: 000 000 000

Field #2: *** *** ***

四、数字变幻

1、减式还原：编写程序求解下式中各字母所代表的数字，不同的字母代表不同的数字。

PEAR

－ ARA ______________ PEA *问题分析与算法设计

类似的问题从计算机算法的角度来说是比较简单的，可以采用最常见的穷举方法解决。程序中采用循环穷举每个字母所可能代表的数字，然后将字母代表的数字转换为相应的整数，代入算式后验证算式是否成立即可解决问题。 *程序与程序注释 #include void main() {

int p,e,a,r;

for(p=1;p<=9;p++) /*从1到9穷举字母p的全部可能取值*/ for(e=0;e<=9;e++) /*从0到穷举字母e的全部可能取值*/ if(p!=e) /*p不等于e*/

for(a=1;a<=9;a++) /*从0到9穷举字母a的全部可能取值*/ if(a!=p&&a!=e)

for(r=0;r<=9;r++) /*从0到9穷举字母r的全部可能取值*/

if(r!=p&&r!=e&&r!=a&&p*1000+e*100+a*10+r-(a*100+r*10+a)

==p*100+e*10+a) {

printf(\%d%d%d%d―n\ printf(\%d%d%d―n\,a,r,a); printf(\

printf(\%d%d%d―n\ } }

*运行结果

PEAR 1098 - ARA - 989 ---------- ------ PEA 109

2、乘式还原

A代表数字0到9中的前五个数字，Z代表后五个数字，请还原下列乘式。

A Z A × A A Z

——————————

A A A A A A Z Z Z A A

——————————

Z A Z A A

#include

void print(long a,long b,long s1,long s2,long s3); int jud(long q,char *pflag); void main() { long i,j,k,l,m,n,term,t1,t2,t3; int flag; for(i=0;i<=4;++i) /*被乘数的第一位*/ for(j=5;j<=9;++j) /*被乘数的第二位*/ for(k=0;k<=4;++k) /*被乘数的第三位*/ { term=100*i+10*j+k; /*被乘数*/ for(flag=0,n=0;n<4&&!flag;) /*乘数的第一位*/ flag=jud((t3=++n*100*term)/100,\判断第三个部分积*/ if(flag) { for(flag=0,m=0;m<4&&!flag;) /*乘数的第二位*/ flag=jud((t2=++m*10*term)/10,\判断第二个部分积*/

if(flag) { for(flag=0,l=5;l<9&&!flag;) /*乘数的第三位*/ flag=jud(t1=++l*term,\判断第一个部分积*/ if(flag&&jud(t1+t2+t3,\判断乘式的积*/ print(term,n*100+m*10+l,t1,t2,t3); } } } }

void print(long a,long b,long s1,long s2,long s3) /*打印结果*/ { printf(\ %ld\\n\ printf(\ %ld\\n\ printf(\\\n\ printf(\ printf(\\\n\ printf(\}

int jud(long q,char *pflag) /*判断一个数的每一位是否满足要求的判断函数*/ /*q:需要判断的数。pflag:标志字符串，A用1表示，Z用0表示。标志串排列顺序：个十百…*/ { while(q!=0&&*pflag!=NULL) /*循环判断对应位的取值范围是否正确*/ if(*pflag-'0'!=(q>=5?1:0)) /*标志位与对应的位不符，返回0*/ return 0; else { q/=10;++pflag; /*若相符则取下一位进行判断*/ } if(q==0&&*pflag==NULL) /*q的位数与标志字符串的长度相同时，返回1*/ return 1; else return 0; }

思考题

E代表数字0到9中的偶数数字，O代表奇数数字，请还原下列乘式。

E E O 2 8 5 × O O 答案 × 3 9 —————– ————— E O E O 2 5 6 5 E O O 8 5 5

—————— ————– O O O O O 1 1 1 1 5

3、质数竖式

下面的竖式是一个乘法运算问题，它的每个＊号可以代入一个数字，这个数字属于一个特定的由N个数字组成的集合。假如这个集合是｛2，3，5，7｝，那么这个竖式称作―质数竖式‖。

* * * X * * --------- * * * * * * ----------- * * * *

写一个程序找出对应于集合｛1，2，3，4，5，6，7，8，9｝的任意一个子集的所有竖式。用集合｛2，3，4，6，8｝和质数集合｛2，3，5，7｝来测试你的程序。运行举例：

ENTER A SET OF DIGITS:23468 2 2 2 X 2 2 ----------

4 4 4 <还有3个竖式未显示> 4 4 4 ---------- 4 8 8 4

The number of unique solutions=4

(1)解题思路

此题比较简单,只需对两个乘数进行循环，然后判定竖式中的数是否满足要求，需注重的一点是：乘积可能超出整型的范围，需要用长整型来计算。 (2)参考程序

Var num:Set Of Byte; {数字集合}

n:视频教程'>word; {竖式的数目} procedure Init; {读入数据并初始化} Var st:String; i:Word; Begin

Write('Enter a set of digits:');

Readln(St); {以字符串的形式读入} Num:=[];

For i:=1 To Length(st) Do

include(Num,Ord(St[i]-Ord('0')); n:=0;

End;

Function Ok(x:Longint):Booklean; {判定x的每位数是否都在集合中} Begin

Ok:=False; While x>0 Do Begin

If Not((x Mod 10)In Num)Then Exit;

x:=x css.shtml' target='_blank' title = 'div视频教程'>div 10; End;

Ok:=True; End;

Procedure Cacl; {找出满足条件的竖式} Var i,j:Longint; Begin

For i:=111 To 999 Do If Ok(i) Then

For j:=11 To 99 Do {对两个乘数进行循环} If Ok(j) And Ok(j Mod 10)*i)And Ok((j Div 10)*i) And Ok(i*j) Then Begin

Inc(n);

Writeln('<',n,'>'); Writeln(i:6); Writeln('X',j:4); Writeln('-----------'); Writeln((i Mod 10)*i:6); Writeln((j Mod 10)*i:6); Writeln((j Div 10)*i:5); Writeln('------------'); Write(i*j:6); End;

Writeln('The number of unique solutions=',n); End; Begin

Init; {读入数据并初始化} Cacl; {找出满足条件的竖式} End.

(3)运行结果

Enter a set of digits:2357 {1}

7 7 5

X 3 3 ---------- 2 3 2 5 2 3 2 5 ----------- 2 5 5 7 5

The number of unique solutions=1

五、数字组合与拆解

1、(2011年预赛题)任何一个自然数m的立方均可写成m个连续奇数之和。例如： 1^3=1 2^3=3+5 3^3=7+9+11 4^3=13+15+17+19

编程实现：输入一自然数n，求组成n^3的n个连续奇数。 #include void main() { int i,j,n,sum,count; printf(\请输入一个整数:\ scanf(\ printf(\ i=1; while(i<=n*n*n) { sum=0; count=0; for(j=i;j<=n*n*n;j+=2) { sum=sum+j; count++; if((n*n*n==sum)&&(count==n)) break; } if((sum==n*n*n)&&(count==n)) break; i+=2; } printf(\

printf(\ while(i

printf(\

}

2、输入一个五位以内的正整数，（1）判断它是一个几位数；（3）逆序输出其各位数字。如输入：56439，输出：5位数 5，6，4，3，9 9，3，4，6，5 #include long power(int n) { int i; long result=1; for(i=1;i<=n;i++)

result=10*result;

return result;

}

void main() { long num,n,j; int count=1,tmpcount;

printf(\请输入一个整数(0-99999):\ scanf(\ n=num;

while((n=n/10)!=0)

count++; printf(\ tmpcount=count; n=num;

while(count-->1)

2）请按序输出其各位数字；（

{ }

printf(\ n=num;

while(tmpcount-->1) { }

printf(\

printf(\ n=n/10; j=power(count); printf(\ n=n%j;

}

3、验证18位证件号：

输入18位证件号，将奇位数的值相加的和求的平均数X，偶位数先与3相乘得到的个位数的和的平均数y。如果（X+Y）是10的倍数，则证件号正确，否则则错误。请编写程序验证证件号是否正确。（12分）列入输入：431023198919230939

输出：正确分析：

奇位数：3 0 3 9 9 9 3 9 9 偶位数：3 0 2 1 8 1 2 1 4

X:（3+0+3+9+9+9+3+9+9）/9 = 6

Y: 3*3 = 9 0*3 = 0 2*3 = 6 1*3 = 3 8*3 = 24 1*3 = 3 2*3 = 6 1*3 = 3 4*3 = 12 (9+0+6+3+4+3+6+3+2)/9 = 4 X+Y = 6+4 = 10

import java.lang.String; import java.util.Scanner; public class Xinyongka {

String str;

Xinyongka(String ss) { }

str=ss;

//public void yanzheng(String s) public void yanzheng() {

//x为某位的数值，OW2为偶数位乘以2，JWsum为奇数位之和，OWsum为偶数位处理后的和

public static void main(String[] args) {

Scanner input = new Scanner(System.in); String s1 = input.next(); // // }

int x,OW2,JWsum=0,OWsum=0; //this.str=s;

for (int i = this.str.length()-1; i >=0 ; i--) { }

System.out.println();

System.out.println(\ sum=\if((OWsum+JWsum)==0) else

System.out.println(\错误！\System.out.println(\正确！\

//System.out.print(str.charAt(i)); //x=Integer.parseInt(str.charAt(i));

x=str.charAt(i)-48; //把数字字符的ASCII值转为它的数值 if((this.str.length()-i)%2==1) else { }

OW2=x*2;

OWsum+=OW2>9?OW2:OW2; JWsum+=x;

Xinyongka xyk = new Xinyongka(s1);

xyk.yanzheng(); } }

4、整数的分划问题。

如，对于正整数n=6，可以分划为： 6 5+1

4+2, 4+1+1

3+3, 3+2+1, 3+1+1+1

2+2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+1+1

现在的问题是，对于给定的正整数n,编写算法打印所有划分。用户从键盘输入 n （范围1~10）程序输出该整数的所有划分。

public class IntegerDivision { /** * @param args */ public static void main(String[] args) { IntegerDivision id = new IntegerDivision(6); int count = id.divInteger(id.getN(), id.getN()); System.out.println(count); } private int n; public IntegerDivision(int _n) { n = _n; } /** * 递归求解 * * @param n * @param m * @return */ public int divInteger(int n, int m) { if (n < 1 || m < 1) { System.out.println(\输出参数错误！\ } else if (n == 1 || m == 1) {

m); }

return 1; } else if (n < m) { return divInteger(n, n); } else if (n == m) { return divInteger(n, n - 1) + 1; } else { return divInteger(n, m - 1) + divInteger(n - m,

}

return 0; }

public int getN() { return n; }

public void setN(int n) { this.n = n; }

5、花朵数：一个N位的十进制正整数，如果它的每个位上的数字的N次方的和等于这个数本身，则称其为花朵数。

例如：

当N=3时，153就满足条件，因为 1^3 + 5^3 + 3^3 = 153，这样的数字也被称为水仙花数（其中，―^‖表示乘方，5^3表示5的3次方，也就是立方）。

当N=4时，1634满足条件，因为 1^4 + 6^4 + 3^4 + 4^4 = 1634。当N=5时，92727满足条件。

实际上，对N的每个取值，可能有多个数字满足条件。

程序的任务是：求N=21时，所有满足条件的花朵数。注意：这个整数有21位，它的各个位数字的21次方之和正好等于这个数本身。

如果满足条件的数字不只有一个，请从小到大输出所有符合条件的数字，每个数字占一行。因为这个数字很大，请注意解法时间上的可行性。要求程序在3分钟内运行完毕。 */

public class Num_of_Flowers { /**

* @param args */

public static void main(String[] args) { // TODO Auto-generated method stub

//0~9 每个数字的21次方

BigInteger[] pw={p(0),p(1),p(2),p(3),p(4),p(5),p(6),p(7),p(8),p(9)};

//0~9每个数字在21位位数中出现的次数 int[] nn=new int[10];

//算法核心：21个名额中：0~9每个数字出现的次数进行“大排列” f(pw,nn,0,0); }

//求解核心：利用递归方式遍历所有数字出现次数的可能 private static void f(BigInteger[] pw, int[] nn, int cur, int use) { // TODO Auto-generated method stub

//选到了最后一个数字 if(cur==9) {

nn[9]=21-use;

ji_suan(pw,nn); return; }

//对当前位置的所有可能进行枚举 for(int i=0;i<21-use;i++) {

nn[cur]=i;

f(pw, nn, cur+1, use+i); } }

//传入的是0~9的各个21次方的值以及每个数字出现的次数。 private static void ji_suan(BigInteger[] pw, int[] nn) { // TODO Auto-generated method stub //求和

BigInteger sum=BigInteger.ZERO; for(int i=0;i<10;i++) {

//求pw[]里面的数字值（已经求了21次方的和）在nn[]中出现的次数，然后再乘积求和

sum=sum.add(pw[i].multiply(BigInteger.valueOf(nn[i]))); }

String s=\

//如果sum的长度小于或大于21，可以直接不用做下一步考虑，直接返回。 if(s.length()!=21) return;

//确定和中各个数字出现多少次 int[] nn2=new int[10];

//统计0~9数字在结果中出现的次数 for(int i=0;i<21;i++) {

nn2[s.charAt(i)-'0']++; }

//测试是否与nn[]中各个对应位置数目相同 for(int i=0;i<10;i++) {

if(nn[i]!=nn2[i])return;

}

//完全匹配！打印结果 System.out.println(s); }

//求x的21次方

private static BigInteger p(int x) { // TODO Auto-generated method stub BigInteger base=BigInteger.ONE;

for(int i=0;i<21;i++) {

base=base.multiply(BigInteger.valueOf(x)); }

return base; } }

6、公倍数

为什么1小时有60分钟，而不是100分钟呢？这是历史上的习惯导致。但也并非纯粹的偶然：60是个优秀的数字，它的因子比较多。

事实上，它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。

我们希望寻找到能除尽1至n的的每个数字的最小整数。

不要小看这个数字，它可能十分大，比如n=100, 则该数为： 69720375229712477164533808935312303556800

请编写程序，实现对用户输入的 n （n<100）求出1~n的最小公倍数。

例如：用户输入： 6

程序输出： 60

用户输入： 10

程序输出： 2520

要求考生把所有函数写在一个文件中。调试好后，存入与考生文件夹下对应题号的―解答.txt‖中即可。