算法设计与分析打印资料.doc

第一章 求二个正整数的最大公约数。main( ) int a,b,t,i; input (a,b); t=1； for (i=2; i=a and i=b; i+) while (a mod i=0 and b mod i=0 ) t=t*i; a=a/i; b=b/i; print(t ,“is maximal common divisor”); 第二章 fact(int n) if (n=0 or n=1) return (1); else return (n*fact(n-1); 第三章完数main( ) int i,k,j,s,a20; for(i=1;i=1000;i+)s=1; k=0; for(j=2;ji;j+) if (i mod j)=0) s=s+j; ak=j; k+; if(i=s) print(s, “its factors are :”,1); for(j=0;ik;j+) print(“,”,ak); 编写算法：打印具有下面规律的图形。 1 5 2 8 6 3 10 9 7 4 main( ) int i,j,a100100,n,k; input(n); k=1; for(i=1;i=n;i=i+1) for( j=1;j=n+1-i;j=j+1) ai-1+jj=k; k=k+1; for(i=1;i=n;i=i+1) print( “n”); for( j=1;j0) 2) hanoi(n-1,a,c,b); 3) 输出 “ Move dise” ,n.”from pile”,a,” to”b); 4) haboi(n-1,c,b,a); 5) endif 从低位到高位逐位输出f1(n) while(n=10) print( n mod 10); n=n10; print(n); 数字翻译称英文main( ) int i,a10, ind; long num1,num2; char eng106=“zero”,”one”,”two”,”three ”,” four”, ” five”,”six”,”seven”,“eight”,”nine”; print(“Input a num”); input(num1); num2=num1; ind =0; while (num20) aind=num2 mod 10; ind= ind +1; num2=num2/10; print(num1, “English_exp:”, engaind-1); for( i=ind-2;i=0;i=i-1) print(“-”，engai); 找钱问题main( ) int i,j,x,y,z,a,b7=0,50,20,10,5,2,1,s7; input(x,y); z=y-x; for(i=1;i=6;i=i+1) a=zbi; si=a; z=z-a*bi; print(y,”-”x,”=”,z:); for(i=1;i=6;i=i+1) if (si0) print(bi, “-”, si); 【例1】 编程打印形如下规律的n*n方阵例如下图：使左对角线和右对角线上的元素为0,它们上方的元素为1,左方的元素为2,下方元素为3,右方元素为4,下图是一个符合条件的阶矩阵。 0 1 1 1 0 2 0 1 0 4 2 2 0 4 4 2 0 3 0 4 0 3 3 3 0main( ) int i,j,a100100,n; input(n); for(i=1;i=n;i=i+1) for(j=1;j=n;j=j+1) if (i=j or i+j=n+1) a ij=0; if (i+jn+1 and ij) a ij=1; if (i+jj) a ij=2; if (i+jn+1 and ij) a ij=3; if (i+jn+1 and ij) a ij=4; for(i=1;i=n;i=i+1) print( “换行符”); for( j=1;j=n;j=j+1) print(aij); 【例2】 螺旋阵：任意给定n值，按如下螺旋的方式输出方阵：n=4 输出： 1 12 11 10 2 13 16 9 3 14 15 8 4 5 6 7 main( ) int i,j,a100100,n,k; input(n); k=1; for(i=1;i=n/2;i=i+1) for( j=i;j=n-i;j=j+1) a ji=k； k=k+1; /左侧/ for( j=i;j=i+1;j=j-1)ajn+1-i=k;k=k+1; /右侧/ for( j= n-i+1;j=i+1;j=j-1) aij=k; k=k+1; /上方/ if (n mod 2=1) i=(n+1)/2; aii=n*n; for(i=1;i=n;i=i+1) print(“换行符”); for( j=1;j=n;j=j+1) print(aij); 【例2】开灯问题：有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉；2号同学将编号为2的倍数的灯都打开；3号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。问经n个同学操作后，哪些灯是打开的？ main( ) int n,a1000,i,k; print(“input a number”); input(“%d”,&n); for( i=1;i=n;i+) ai=0; for( i=2;i=n;i+) k=1; while ( i*k=n) ai*k=1-ai*k; k=k+1; for( i=1;i=n;i+) print( ai); 【例4】编写算法，求任意三个数的最小公倍数。 main( ) int x1,x2,x3,t=1,i,flag,x0; print(“Input 3 number:”); input(x1,x2,x3); x0=max(x1,x2,x3); for (i=2;iy&xz) return(x); else if(yx and yz) return(y); else return(z); 例1】警察局抓了a，b，c，d四名偷窃嫌疑犯，其中只有一人是小偷。审问中 a说：“我不是小偷。” b说：“c是小偷。”c说：“小偷肯定是d。” d说：“c在冤枉人。”现在已经知道四个人中三人说的是真话，一人说的是假话，问到底谁是小偷？main( ) int x; for(x=1;x=4;x+) if(x1)+(x=3)+(x=4)+(x4)=3) print(chr(64+x),“is a thief .”); 运行结果： c is a thief . 【例2】三位老师对某次数学竞赛进行了预测。他们的预测如下： 甲说：学生A得第一名，学生B得第三名。乙说：学生C得第一名，学生D得第四名。丙说：学生D得第二名，学生A得第三名。竞赛结果表明，他们都说对了一半，说错了一半，并且无并列名次，试编程输出A、B、C、D各自的名次。main( ) int a,b,c,d; for( a=1;a=4;a=a+1) for( b=1;b=4;b=b+1) if (ab) for( c=1;c=4;c=c+1) if (ca and cb) d=10-a-b-c; if (da and db and dc ) if(a=1)+(b=3)=1 and (c=1)+(d=4)=1 and (d=2)+(a=3)=1) print( “a,b,c,d=”,a,b,c,d); 问题描述：一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问一年中每个月各有多少只兔子。main( ) int i,a=1,b=1; print(a,b);for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； 最大公约数main（） int a, b; input(a,b); if(b=0) print(“data error”); return; else c = a mod b;while c0 a=b; b=c; c=a mod b; print(b);【例1】百钱百鸡问题。中国古代数学家张丘建在他的算经中提出了著名的“百钱百鸡问题”：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，翁、母、雏各几何?main( ) int x,y,z;for(x=1;x=20;x=x+1) for(y=1;y=34;y=y+1) for(z=1;z=100;z=z+1) if(100=x+y+z and 100=5*x+3*y+z/3) print(the cock number is,x)； print(the hen number is, y)；print(the chick number is z);【例2】解数字迷： A B C A B A D D D D D D main（ ） long A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A=9; A+) for(B=0; B=9; B+) for(C=0; C=9; C+) F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i=5; i+) G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6) print( F，”*”，A，”=”，E); P136 公倍数【例3】狱吏问题 main1( )int *a,i,j,n;input(n); a=calloc(n+1,sizeof(int); for (i=1; i=n;i+) ai=1; for (i=1; i=n;i+) for (j=i; j=n;j=j+i) aj=1-aj; for (i=1; i=n;i+) if (ai=0) print(i,”is free.”);一组数据最大最小、一组数第二小 算法2 递归求取最大和最小元素 float an;maxmin （int i, int j ,float &fmax, float &fmin）int mid; float lmax, lmin, rmax, rmin;if (i=j) fmax= ai; fmin=ai;else if (i=j-1) if(airmax) fmax=lmax; else fmax=rmax; if(lminrmin) fmin=rmin; else fmin=lmin; 求一组数的第二小的数。 float a100;main( ) int n; float min2; input(n); for (i=0;i=n-1;i=i+1) input(ai); min2=second(n);print(min2); second（int n） float min2,min1; two(0,n-1, min2, min1);return min2;two（int i, int j，float &fmin2, float &fmin1） float lmin2,lmin1,rmin2,rmin1; int mid; if （i=j） fmin2=fmin1=ai else if (i=j-1) if(aiaj) fmin2=aj；fmin1=ai; else fmin2=ai; fmin1=aj; else mid=(i+j)/2; two（i，mid，lmin2，lmin1）; two（mid+1，j，rmin2，rmin1）; if (lmin1rmin1) if (lmin2rmin1 & (i!=mid) fmin1=lmin1;fmin2=lmin2; else fmin1=lmin1; fmin2=rmin1; else i