|
例4.12 求S=1!+2!+3!+....+10! 分析：这个问题是求10以内自然数的阶乘之和，可以用for循环来实现。程序结构如下： for(i=1;i<=10;++i) { (1)i阶乘的值存到t； //t=i! (2)累加t到s中； //s+=t } 显然根据以上结构，通过10次的循环可以求出1！，2！，…10!,并不断累加起来，求出s。而求t=i!,又可以用一个for循环来实现： t=1; for (j=1;j<=i;++j) t*=j; 因此整个程序为： #include using namespace std; int main (){ int t,s; s=0; for(int i=1;i<=10;++i) { t=1; for (int j=1;j<=i;++j) //求i! t*=j; s+=t; //累加i! } cout< return 0; } 以上程序是一个for循环的嵌套。这种方法是比较容易想到的，但实际上对于求i！，我们可以根据求出的（i-1）！乘上i即可得到，而无需重新从1再累乘到i。 因此程序可改为: #include using namespace std; int main () { int t=1,s=0; for(int i=1;i<=10;++i) { t*=i; //t为上一个数的i-1的阶乘值，再乘以i即为i! s+=t; //累加i! } cout< return 0; } 显然第二个程序的效率要比第一个高得多。第一个程序要进行1+2+3+…+10=55次循环，而第二程序进行10次循环。若题目中求的是1！+2！+…+1000！，则两个程序的效率区别更明显。 例4.13 一个炊事员上街采购，用500元钱买了90只鸡，其中母鸡一只15元,公鸡一只10元，小鸡一只5元，正好把钱买完。问母鸡，公鸡，小鸡各买了多少只？ 【分析】设母鸡i只,公鸡j只,则小鸡为90-i-j只,则15*i+ 10* j+(90-i-j)*5=500,显然一个方程求两个未知数是不能直接求解。必须组合出所有可能的i,j值，看是否满足条件。这里i的值可以是0到33，j的值可以0到50。源程序如下： #include using namespace std; int main () { int k; for (int i=0;i<=33;++i) //枚举母鸡的数量 for (int j=0;j<=50;++j) //枚举公鸡的数量 { k=90-i-j; if (15*i+10*j+k*5==500) { cout<<'母鸡有'< } } return 0; } 例4.14 利用for循环语句输出图4-1中的三角形。 * ** *** **** ***** #include using namespace std; int main () { for (int i=1; i<=5; ++i) //控制行数 { for (int j=1; j<=i; ++j) //输出一行中的*数 cout<<'*'; cout< } return 0; } 例4.15 求100－999中的水仙花数。若三位数ABC，ABC=A3+B3+C3，则称ABC为水仙花数。 例如153，13+53+33=1+125+27=153，则153是水仙花数。 【分析】根据题意，采用三重循环来求解。由于循环次数一定，用for循环最为简单。程序如下： #include #include using namespace std; int main() { for (int a=1; a<=9; ++a) for (int b=0; b<=9; ++b) for (int c=0; c<=9; ++c) { if (a*a*a+b*b*b+c*c*c==a*100+b*10+c) cout< } return 0; } 运行结果： 153370371407 同时也可以采用一个for循环来求解，表面上看好像优于三重循环，实际上却比上面的程序效率低，请同学们自己分析。 程序如下： #include #include using namespace std; int main() { int a,b,c; for (int m=100; m<=999; ++m) { a=m/100; //m的百位 b=(m%100)/10; //m的十位 c=m%10; //m的个位 if (a*a*a+b*b*b+c*c*c==m) cout< } return 0; } 例4.16 输出100—200中所有的素数。 分析：我们可对100-200之间的每一个整数进行判断，若它是为素数，则输出。而对于任意整数i，根据素数定义，我们从2开始，到sqrt（i），找i的第一个约数，若找到第一个约数，则i必然不是素数。 程序如下： #include #include using namespace std; int main () { intx; for(int i=100;i<=200;++i) { x=2; while(x<=floor(sqrt(i))&&(i%x!=0)) //floor为取整函数，需调用math.h库 x=x+1; //在枚举的范围内并且没有出现约数则继续枚举 if ( x>floor(sqrt(i))) cout< } return 0; } 例4.17 输出所有形如aabb的四位完全平方数（即前两位数字相等，后两位数字也相等）。 【分析】 分支和循环结合在一起时威力特别强大：我们枚举所有可能的aabb，然后判断它们是否为完全平方数。注意，a的范围是1～9，b可以是0。主程序如下： for (a=1; a<=9; a++) for (b=0; b<=9; b++) if (aabb是完全平方数) printf('%d\n',aabb); 另一个思路是枚举平方根x，参考程序如下： #include int main() { intn=0,hi,lo; for(int x=1 ; ; ++x) //可以直接从x=32开始枚举 { n=x*x; if(n<1000) continue; if(n>9999) break; hi= n/100; lo= n%100; if(hi/10 == hi%10 && lo/10 == lo%10) printf('%d\n',n); } return0; } 例4.18 阶乘之和 输入n，计算S=1! + 2! + 3! + … + n!的末6位(不含前导0)。n<=106， n!表示前n个正整数之积。 样例输入：10 样例输出：37913 【分析】 这个任务并不难，引入累加变量S之后，核心算法只有一句话：for (i=1;i<=n;i++) S+=i!。不过C++语言并没有阶乘运算符，所以这句话只是伪代码，而不是真正的代码。事实上，我们还需要一次循环来计算i!：for (j=1;j<=i;++j) factorial*=j;。代码如下： #include int main() { intn,s=0; scanf('%d',&n); for(int i=1;i<=n;++i) { intfactorial=1; for(int j=1;j<=i;++j) factorial*=j; s+=factorial; } printf('%d\n',s%1000000); return0; } 注意累乘器factorial(英文“阶乘”的意思)定义在循环里面。换句话说，每执行一次循环体，都要重新声明一次factorial，并初始化为1(想一想，为什么不是0)。因为只要末6位，所以输出时对106取模。 当n=100时，输出-961703，直觉告诉我们：乘法溢出了。这个直觉很容易通过“输出中间变量”法得到验证，但若要解决这个问题，还需要一点数学知识。试一下n=106时输出什么？更会溢出，但是重点不在这里。事实上，它的速度太慢！让我们把程序改成“每步取模”的形式，然后加一个“计时器”，看看它到底有多慢。 #include #include int main() { constint MOD=1000000; intn,s=0; scanf('%d',&n); for(int i=1;i<=n;++i) { intfactorial=1; for(int j=1;j<=i;++j) factorial=(factorial*j%MOD); s=(s+factorial)%MOD; } printf('%d\n',s); printf('Timeused= %.2lf\n',(double)clock()/CLOCKS_PER_SEC); return0; //输出时间包含键盘输入的时间，建议用文件输入输出，后面章节介绍文件 } 这个程序真正的特别之处在于计时函数clock()的使用。该函数返回程序目前为止运行的时间。这样，在程序结束之前调用它，便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。 输入100000，按Enter键，系统迟迟不输出答案，原因在于程序中重复进行了多次阶乘运算，浪费了大量时间，具体优化方法请参考例4.12 。 【上机练习4.4】 1、求s=11+22+33+..+NN 2、求s=1+1/2!+1/3!+…+1/10! 3、输入一个整数，若是素数，输出“YES”，否则输出“NO” 4、任给一个自然数n，求出这个自然数不同因数的个数。 如：n=6时，因为1，2，3，6这四个数均是6的因数，故输出为total=4。 5、输入一列图形（字母金字塔） a a b a b c . . a b c …… y z 6、把一张一元钞票换成一分，二分和五分的硬币，每种至少一枚。问有哪几种换法？ 7、百鸡问题：一只公鸡值5元，一只母鸡值3元，而1元可买3只小鸡。现有100元钱，想买100只鸡。问可买公鸡、母鸡、小鸡各几只？ 8、某人想将手中的一张面值100元的人民币换成10元、5元、2元和1元面值的票子。要求换正好40张，且每种票子至少一张。问：有几种换法？应适当考虑减少重复次数。 9、有一堆100多个的零件，若三个三个数，剩二个；若五个五个数，剩三个；若七个七个数，剩五个。请你编一个程序计算出这堆零件至少是多少个？ 10、编写一程序，验证角谷猜想。所谓的角谷猜想是：“对于任意大于1的自然数n，若n为奇数，则将n变为3*n+1，否则将n变为n的一半。经过若干次这样的变换，一定会使n变为1。” 11、哥德巴赫猜想（任何充分大的偶数都可由两个素数之和表示）。将4-100中的所有偶数分别用两个素数之和表示。输出为： 4=2+2 6=3+3 … 100=3+97 |
|
|
