CC++数据结构一点经典题目.doc

Test2-4 个人所得税的计算（if-else-if）#include using namespace std;/个人所得税的计算int main()float income,taxable,tax;coutincome;taxable=income-3500;if(taxable=0)tax=0;else if(taxable=1500)tax=taxable*0.03;else if(taxable=4500)tax=taxable*0.1-105; else if(taxable=9000) tax=taxable*0.2-555; else if(taxable=35000)tax=taxable*0.25-1005; else if(taxable=55000) tax=taxable*0.3-2755; else if(taxable=80000) tax=taxable*0.35-5505; else tax=taxable*0.45-13505;coutTax libility is tax算出year这一年元旦星期几2根据mouth和day，计算该日期是year这一年的第几天#include using namespace std;/计算某天是星期几int main()int year,mouth,day,week,d;cout请按 年 月 日 的方式输入一个日期：yearmouthday;d = year+(year-1)/4-(year-1)/100+(year-1)/400;week=d%7;d=0;switch(mouth-1)case 11:d+=30;case 10:d+=31;case 9:d+=30;case 8:d+=31;case 7:d+=31;case 6:d+=30;case 5:d+=31;case 4:d+=30;case 3:d+=31;case 2:d+=28;if(year%4=0 & year%100!=0 | year%400!=0) d+; /判断是否是闰年case 1:d+=31;d+=day;week=(week+(d-1)%7)%7;if(week=0)coutyear年mouth月day日是星期日endl;elsecoutyear年mouth月day日是星期weekendl;return 0;Test2-6 找到最小值和最大值（for）#include using namespace std;/找最大数和最小数（循环）int main()int x,max,min;cout请依次输入5个数（空格隔开）：x; /输入一个数max=min=x;for(int i=2;ix;if(maxx) min=x;cout最大值为MAX=max,最小值为MIN=minendl;return 0;Test2-7 选票统计（switch-case）#include using namespace std;int main()int sele,zhang,li,wang,nosele,other,num;zhang=li=wang=nosele=other=0;cinsele;while(sele!=-1)switch(sele)case 1:zhang+;break; /当输入为1时，为zhang投票case 2:li+;break; /当输入为2时，为li投票case 3:wang+;break;case 0:nosele+;break; /弃权为0case 4:other+;break; /无效票（选择人数超过一）default:coutInput Error!sele;num=zhang+li+wang+nosele+other; /请问弃权和无效的票算不算其中float z,l,w;z=zhang/(float)num;l=li/(float)num;w=wang/(float)num;coutzhang:zhang，得票率：zendl;coutli:li，得票率：lendl;coutwang:wang，得票率：wendl;Test2-8 逆序数（do-while）#include using namespace std;/逆序数的输出（第一个do-while判断是否为非负整数，第二个do-while进行逆序数的转换）int main()int number,digit;docoutnumber;while(number0);coutnumber的逆序数是：;dodigit=number%10;number/=10;cout0);coutendl;return 0;Test2-9 求出最小爱因斯坦阶梯数-方式1（do-while）#include using namespace std;/判断最小的爱因斯坦阶梯数int main()int x=1;dox+;while(!(x%2=1 & x%3=2 & x%4=3 & x%5=4 & x%6=5 & x%7=0); /非常综合的式子cout爱因斯坦的阶梯数为：xendl;return 0;Test2-9-1 求出最小爱因斯坦阶梯数-方式2（while、if-else）#include using namespace std;/判断最小的爱因斯坦及阶梯数-方式2int main()int x=7;while(1)if(x%2=1 & x%3=2 & x%4=3 & x%5=4 & x%6=5 & x%7=0) break;else x+=7;cout爱因斯坦的阶梯数为：xendl;return 0;Test2-10 z字排列的数表，输入一个数，找出改位置的数（for）#include using namespace std;/z字排列的数表，输入一个数，找出改位置的数int main()int i,n,k;cinn;for(i=1;i=n;i+)for(int j=1;j=n;j+)couti/j ;coutendl;for(i=1;i*(i+1)/2n;i+);k=n-(i*(i-1)/2);if(i%2!=0)couti+1-k/kendl;elsecoutk/i+1-kendl;return 0;Test2-11 将1元兑换成1分，2分，5分的硬币，共有多少种兑换的方法（for两层）#include using namespace std;/人民币兑换(将1元兑换成1分，2分，5分的硬币，共有多少种兑换的方法)int main()int five,two,count;count=0;for(five=0;five=100/5;five+)for(two=0;two=(100-5*five)/2;two+)count+;cout共有count种兑换方法！endl;return 0;Test2-12 分解质因数（while、if-else）#include using namespace std;/分解质因数int main()int n,i;coutn;coutn=;i=2;while(in)if(n%i=0)couti*;n=n/i;else i+;coutnendl;return 0;Test2-13 10000内完全数的枚举（for）#include #include using namespace std;/求10000以内的完全数（真因子之和为次数本身）int main()int i,n,s,cnt=0;for(n=2;n=10000;n+)s=1;for(i=2;i=sqrt(n);i+)if(n%i=0)if(i!=n%i) s=s+i+n/i;else s+=i;if(s=n)cnt+;cout第cnt个完数;coutn =1;for(i=2;i=sqrt(n);i+)if(n%i=0)cout+i+n/i;coutendl;return 0;Test2-14 求100,200之间质数#include #include /求100,200之间的质数using namespace std;int main()int i,k,m,s;for(m=101;m=200;m=m+2)k=sqrt(m);s=0;for(i=2;i=k;i+)if(m%i=0)s=1;break;if(s=0) coutm ;coutendl;return 0;*Test2-15 乘积全是1（do-while）#include using namespace std;/键盘输入一个奇数p（末尾不是5），总有一个数t使得p*t=1111.111int main()int p,a,b,r,t,n;while(1) /判断输入的数是否满足要求cout输入自然数p，最后一位是3或5或7或9：endl;coutp;if(p%2!=0&p%5!=0) break;a=0;n=0;while(a=p的一个全为1的数aa=a*10+1;n+;t=0;couts=;do /此处代码深奥，王细细理解（以p=3为例）b=a/p;coutb;t+;if(t%50=0) coutendl0);coutendln=-nendl;return 0;*Test2-16 尼科彻斯定理：（for）#include using namespace std;/尼科彻斯定理：任何一个整数的立方都可以表示为一连串连续的奇数之和int main()int n,num,sum,i,j,flag;coutn;num = n*n*n;flag=0;for(i=1;inum & flag=0;i+=2)sum=0;for(j=i;jnum;j+=2)sum+=j;if(sum = num)coutnum=i+i+2+.+j num) break;return 0;Test2-17 末尾0的个数：（for-while）#include using namespace std;/对任意给定的正整数你，求n!中末尾0的个数int main()int i,j,k=0,n;cinn;for(i=5;i=n;i=i+5)j=i;while(j%5=0)k+;j=j/5;coutn!末尾0的个数为k结果）和逆推（结果-条件）Test2-18 走楼梯（for）#include using namespace std;/走楼梯，按照1,2,3的阶梯数走完n个阶梯的方法有多少种。int main()int a,b,c,d,i,n;coutn;a=1;b=2;c=4;if(n=0)cout楼梯阶数应为正整数，输入错误！endl;elseif(n=1) d=a;else if(n=2) d=b;else if(n=3) d=c;elsefor(i=4;i=4时，满足以下条件，d=a+b+c;a=b; b=c; c=d;cout走完n级楼梯的全部走法有d种。endl;return 0;Test2-19 RPG涂色问题#include using namespace std;/RPG涂色问题：一行n个方格，用红、粉、绿涂色，每个格子一色，/相邻不能同色，首尾不能同色（0n=30）int main()int i,n,f1,f2,f3,num;cout请输入方格数目n（0nn;if(n=1) num=3;else if(n=2|n=3) num=6;elsef1=6; f2=6;for(i=4;i=4时，会有如下方法f3=2*f1+f2;f1=f2;f2=f3;num=f3;coutn个方格的正确涂色方案一共有num种。endl;/方法二：更直观。int j,m,f31;f0=0;f1=3;f2=f3=6;for(j=4;j31;j+)fj=fj-1*2+fj-2;cout请输入方格数目m（mm;coutm个方格的正确涂色方案一共有fm种。endl;return 0;*Test2-20 马的行走路径#include using namespace std;/马行走的路径：规则：1.马走日字;2.马只能向右走int main()int dx5=0,2,2,1,1,dy5=0,1,-1,2,-2;struct pointint x;int y;point a5151;int i,j,n,m,k;for(i=0;i51;i+)for(j=0;j51;j+)aij.x=aij.y=0;coutnm;anm.x=-1; /标记为终点anm.y=-1;for(i=n;i=2;i-) /倒推for(j=1;j=m;j+)if(aij.x!=0)for(k=1;k=4;k+)ai-dxkj-dyk.x=i;ai-dxkj-dyk.y=j;if(a11.x=0)coutNo!endl;else /存在路径i=1;j=1;cout(i,j);while(aij.x!=-1)k=i;i=aij.x;j=akj.y;cout(i,j);coutendl;return 0;Test2-21 储油点#include using namespace std;/穿过1000km沙漠，储油点的选择int main()int k; /储油点位置序号float d,d1; /d为终点至当前储油点的距离，d1:i=n至始点的距离float oil10,dis10; /dis为各储油点到终点的距离int i;cout序号t离出发点距离(km)t储油量(L)endl;k=1;d=500; /从i=1处开始向始点倒推dis1=500;oil1=500;/离终点最近的储油点作为递推的开始dok+=1;d+=500/(2*k-1);disk = d;oilk = oilk-1+500;while (d1000); /递推结束条件为储油点到终点的距离超过1000disk=1000; /置始点至终点的距离值d1=1000-disk-1; /求储油点k处至始点的距离oilk = d1*(2*k+1)+oilk-1; /求始点藏油量for(i=0;ik;i+)coutit1000-disk-itttoilk-iendl;return 0;*Test2-22 乘火车（看懂看，看不懂算）#include #include using namespace std;/测试数据：10 15 530#define MAXS 101int main()int a,n,m,k,i;int pMAXS,downMAXS,upMAXS;cout请输入车站数n，始发站上车人数a和终点站下车人数m：nam;up1=a;down1=0;p1=a;k=1;doup2=k;down2=k;p2=p1; /枚举第二站的上下车人数和车上人数for(i=3;in;i+) /递推第三站.第n-1站的车上人数upi=upi-1+upi-2;downi=upi-1;pi=pi-1+upi-2;if(pn-1=m) /若n-1站车上人数为m，则输出从各站开出时车上的人数upn=0;downn=m;pn=0;cout上车情况如下：endl;cout车站编号：;for(i=1;i=n;i+)coutsetw(4)i ;coutendl;cout上车人数：;for(i=1;i=n;i+)coutsetw(4)upi ;coutendl;cout下车人数：;for(i=1;i=n;i+)coutsetw(4)downi ;coutendl;cout车上人数：;for(i=1;i=n;i+)coutsetw(4)pi ;coutendl;break;k=k+1; /第二站上车人数增加1while(pn-1m) coutNo Answer!endl;return 0;迭代法又称为辗转法：不断用变量的旧值推出新值1. 确定迭代变量；2. 建立迭代关系；3. 对迭代进行控制。Test2-23 验证“谷角猜想”（while）#include using namespace std;/验证“谷角猜想”：一个自然数n，n为偶数/2给n（循环），n为奇数*3+1；/再/2,（循环），总可以得到自然数1int main()unsigned int data;coutdata;while(data!=1)if(data%2=0)coutdata/2=;data/=2;coutdataendl;elsecoutdata*3+1=;data=data*3+1;coutdataendl;return 0;Test2-24 埃及分数（分子为1的分数（又叫单位分数）#include using namespace std;/埃及分数（就是单位分数）/设a、b为互质正整数，且ab，将a/b化为若干个埃及分数之和int main()int a,b,c;coutab;couta/b=;while(b%a!=0)c=b/a+1;cout1/c+;a=a*c-b;b=b*c;cout1/b/aendl;return 0;Test2-25 求平方根#include #include using namespace std;/求平方根int main()double x0,x1,a;cina;x0=a/2; /迭代初值x1=0.5*(x0+a/x0);dox0=x1; /为下一次迭代做准备x1=0.5*(x0+a/x0);while(fabs(x1-x0)0.000001);coutx1endl; /输出结果return 0;Test2-26 迭代求解方程的根#include #include using namespace std;/迭代法求方程根int main()/解法一（二分迭代）double x1,x2,x3;x1=0;x2=2; /初始区间dox3=(x1+x2)/2;if(x1*x1*x1-x1-1)*(x3*x3*x3-x3-1)0)x1=x3; /改变区间elsex2=x3; /改变区间while(fabs(x2-x1)0.000001); /判断是否满足精度要求coutx10.000001);/判断是否满足精度要求cout方程的一个根为：y20.000001);cout方程的一个根为：zendl;return 0; Test2-27 水手分椰子（递推和迭代的比较）#include using namespace std;/当然也可以用倒推和迭代的方法（以下为顺推）int main()int i,k,x,y7;k=4;y1=k;i=2;while(i=6)if(4*yi-1-1)%5!=0)k+=5;y1=k;i=2;elseyi=(4*yi-1-1)/5; i+;x=5*y1+1;cout原有的椰子至少x个。endl;for(i=1;i=5;i+)cout第i个水手面临椰子5*yi+1个，藏了yi个。endl;cout最后一起分时有椰子5*y6+1个，每人分得y6个。endl;return 0;穷举法：举例全部可能情况，逐个判断哪些符合问题的求解（例：test2-9）Test2-28 百钱买百鸡（穷举）#include using namespace std;/百钱买百鸡（公鸡/5,母鸡/3,雏鸡3个/1）int main()int x,y,z,cnt;cnt=0;for(x=0;x=100/5;x+)for(y=0;y=(100-5*x)/3;y+)z=100-x-y;if(z%3!=0) continue;if(5*x+3*y+z/3=100)coutx y zendl;cnt+;cout共有买法cnt种。endl;return 0;Test2-29 水仙花数（穷举）#include using namespace std;/找出(100,1000)之间的水仙花数（n的各位数立方之和=n）int main()/解法一int n,a,b,c;for(n=100;n1000;n+)a=n/100;b=n/10%10;c=n%10;if(a*a*a+b*b*b+c*c*c=n)coutn;coutendl;/解法二for(a=1;a=9;a+)for(b=0;b=9;b+)for(c=0;c=9;c+)n=100*a+10*b+c;if(a*a*a+b*b*b+c*c*c=n)coutn ;coutendl;return 0;Test2-30 4位分段和平方数（穷举法）#include #include using namespace std;/四位分段和平方数：例子：2025=(20+25)*(20+25)int main()/解法一int a,b,n;cout解法一（穷举法）：;for(n=1000;n=9999;n+)a=n/100;b=n%100;if(a+b)*(a+b)=n)coutn ;coutendl;/解法二int a1,n1,x,y;cout解法二（自己看）：;for(a=(int)sqrt(1000);a=(int)sqrt(9999);a+)n1=a*a;x=n1/100;y=n1%100;if(a=x+y)coutn1 ;coutendl;return 0;Test2-31 疑案分析（穷举法中的逻辑推理）#include using namespace std;/逻辑推理（01）int main()int a,b,c,d,e,f,cc1,cc2,cc3,cc4,cc5,cc6,g;for(a=0;a=1;a+) /for是为了穷举64种情况（2的6次方）for(b=0;b=1;b+)for(c=0;c=1;c+)for(d=0;d=1;d+)for(e=0;e=1;e+)for(f=0;f=1;f+) /满足的判断条件cc1=a|b;cc2=!(a&d);cc3=(a&e)|(a&f)|(e&f);cc4=(b&c)|(!b&!c);cc5=(c&!d)|(!c&d);cc6=d|(!e);/*全部为真*/ if(cc1+cc2+cc3+cc4+cc5+cc6=6)coutThese man are ;if(a=1) coutA ;if(b=1) coutB ;if(c=1) coutC ;if(d=1) coutD ;if(e=1) coutE ;if(f=1) coutF ;coutendl; /*让有解标志为1*/g=1;if(g!=1) coutCant found!endl; /若无解，输出无解信息return 0;Test2-32 比赛预测（穷举法中的逻辑推理）#include using namespace std;/比赛预判int main()int a,b,c,d,e,cc1,cc2,cc3,cc4,cc5,g;for(a=1;a=5;a+)for(b=1;b=5;b+)for(c=1;c=5;c+)for(d=1;d=5;d+)e=15-(a+b+c+d); /4位选手没取的名次就是e的名次if(e5) continue;/e的名次必须在1,5if(a*b*c*d*e!=120) continue;/5位选手的名次必须各不相同cc1=(b=2)+(a=3)=1;cc2=(b=2)+(e=4)=1;cc3=(c=1)+(d=2)=1;cc4=(c=5)+(d=3)=1;cc5=(e=4)+(a=1)=1;if(cc1+cc2+cc3+cc4+cc5=5)/全部为真coutA is aendl;coutB is bendl;coutC is cendl;coutD is dendl;coutE is eendl;g=1; /有解标志位if(g!=1) coutCant found!endl; /无解return 0;Test2-33 数学趣题：四方定理（穷举法）#include using namespace std;/四方定理：所有自然数至多只要四个数的平方和就可以表示int main()int a,b,c,d,n;coutn;for(a=1;a=n/2;a+) /对a,b,c,d进行穷举for(b=0;b=a;b+)for(c=0;c=b;c+)for(d=0;d=c;d+)if(a*a+b*b+c*c+d*d)=n)couta*a+b*b+;coutc*c+d*d=nendl;return 0; Test2-34 对调数（穷举）#include using namespace std;/对调数：（两位数个位与十位对调产生的新数）int main()int n,n1,a,b,a1,b1,z,z1,cnt=0;while(1) /判断输入时都正确coutn;if(n%10=0 | n=100)cout输入错误！endl;continue; /直接走while循环elsea=n/10;b=n%10;z=b*10+a;break; /跳出循环for(n1=11;n1=99;n1+) /穷举if(n1%10=0) continue; /排除个位=0的a1=n1/10;b1=n1%10;z1=b1*10+a1;if(n+n1)=(z+z1) & n!=z1)coutn + n1 = z + z1endl;cnt+;cout共有cnt个配对！endl;if(cnt=0)cout所求的对调数不存在！endl;return 0;*Test2-35 亲和数#include #include using namespace std;/a的真因子之和=b，b的真因子之和=a，则a，b为一对亲和数int main()unsigned int i,n,s,m,k;int cnt=0;for(n=2;n=10000;n+)s=1;/s为n的真因子之和k=1;/k为n的真因子个数for(i=2;i=sqrt(n);i+)/求解真因子之和if(n%i=0)s=s+i+n/i;k+=2;if(k=1|s=n) continue;/若n为质数|s=n，进行下次循环m=1; /m为s的真因子之和for(i=2;i=sqrt(n);i+)if(s%i=0)m+=i+s/i; /计算s的真因子之和if(m=n) /如果两数相等，输出亲和数cnt+;cout第cnt对亲和数！endl;coutn:1;for(i=2;i=sqrt(n);i+)if(n%i=0)cout+i+n/i;cout=sendl;couts:1;for(i=2;i=sqrt(n);i+)if(s%i=0)cout+i+s/i;cout=nendl;return 0;*Test2-36 三个是三位数#include using namespace std;/1到9九个数字组成三个三位数，且构成1:2:3的形式int main()int a9,x,cnt,i,j,flag;