四月初就听说有个"计算机程序设计大赛", 原本以为只是系里的一个小竞赛, 做个WinForm小程序啥的, 所以到辅导员那边报了名, 这一个来月的时间大部分都花在VB.NET和C#上了. 今天上午去学校主页"公布栏"里才得知学校在选拔ACM的队伍, 尽管入选希望渺茫, 但辅导员已经把俺名单报上去了, 没有办法了, 去凑个热闹, 如果在学校里的选拔竞赛中名次还可以的话, 可以拿个奖状什么的:-)但去了也不能给俺们院的人丢脸, 初赛就交个大白卷吧...希望能熬到决赛塞...
于是乎, 中午11点就去图书馆找<ACM竞赛题>之类的书...不幸的是早已被别人借空...于是上网查电子文档啥的, 找到了一个2009ACM初赛选拔题. 下午上完课之后来到图书馆静心的做题, 发现题目很简单啊. 什么"水仙花数" 不都是老题目了么...
不废话了, 贴上我的代码, 我觉得我的算法很别捏, 感觉很"直", 没有太多高级的想法在里面. 希望各路高人有空瞅瞅...给我指点指点:-)
一、完数
数的因子就是所有可以整除这个数的数,但是不包括这个数自身。比如15的因子是1, 3, 5 。如果一个正整数如果正好等于它的所有因子之和，这个数就称为“完数”。例如，6的因子为1, 2, 3, 而6＝1＋2＋3，因此6是“完数”。请输出1000以内这样的完数
我的思路: 先找出某个数的所有因子, 然后把这些因子加起来, 判断等不等于原数, 等于就输出.
#include<math.h>
using namespace std;
int a, b, c, d;
void func(float n)
{
a = int(sqrt(n)); //对一个数,最多判断n开平方次
for(b = 1; b <= a; b++)
{
c = int(n)%b;
if (c == 0) //说明n能被b整除
d += b + n/b;
}
d = d - n; //因为题目中说因子不包括它本身
if (d == n)
cout << n << endl;
}
int main()
{
float i;
for( i = 0; i <1000; i++)
{
func(i);
d = 0;
}
return 0;
}
输出:
0
1
6
28
496
二、水仙花数
所谓“水仙花数”是指一个3位数，其各位数字的立方之和等于该数本身。 例如，153是一水仙花数，因为153＝1的三次方＋5的三次方＋3的三次方。请输出所有的“水仙花数”
我的思路: 用a表示这个三位数的个位数, b表示十位数, c表示百位数(这边感觉算法不好!), 最后d表示a, b, c的立方和, 判断d和原三位数相不相同, 相同就输出.
using namespace std;
int a, b, c, d;
void func(int n)
{
a = n % 10; //得到个分位的数
b = ((n - a)%100)/10; //得到十分位的数
c = (n - b*10 - a)/100; //得到百分位的数
d = a*a*a+b*b*b+c*c*c; //求出各个数的立方之和
if (d == n)
cout << n << endl;
}
int main()
{
int i;
for( i = 100; i <1000; i++)
func(i);
return 0;
}
输出:
153
370
371
407
三、走楼梯 (这题做的很纠结, 因为答案可能是错的)
楼上走到楼下共有h个台阶，每一步有3种走法：走1个台阶；走2个台阶；走3个台阶。问可走多少种方案？
样例输入：10
样例输出：230
我的思路: 我想通过嵌套循环找出所有可能的组合, 这个组合用oneStep表示走一步的个数, twoStep表示走两步的个数, threeStep表示走三步的个数, 满足关系oneStep*1 + twoStep*2 + threeStep*3 = 台阶数h. 然后知道个这个组合, 再算出有多少种先后顺序. 这样就比如有oneStep个红球, twoStep个绿球, threeStep个蓝球, 一共有多少种排序方法. (这个排序方法我忘了高中时怎么算的了, 遂向QQ群, QQ问问, 我的广大同学请教. 后来QQ问问上有了6条回复, 对了一半, 我同学的同学发来照片(下面有图)...把表达式写在了纸上, 在此感谢那位同学...), 最后用total累计共多少种方法
int func(int i) //求i的阶乘
{
int a = 1, b = 1;
for(;b <= i; b++)
a *= b;
return a;
}
int main()
{
int oneStep, twoStep, threeStep, d, e, h, total=0;
cin >> h;
for(oneStep = 0; oneStep <= h; oneStep++)
{
for(twoStep = 0; twoStep <= (h - oneStep)/2; twoStep++)
{
for(threeStep = 0; threeStep <= (h - oneStep - 2*twoStep)/3; threeStep++)
{
if ((oneStep + 2*twoStep + 3*threeStep) == h) //此时oneStep个1步twoStep个2步和threeStep个三步加起来等于h个台阶
{
d = func(oneStep + twoStep + threeStep)/(func(oneStep)*func(twoStep)*func(threeStep));//此时oneStep个1步twoStep个2步和threeStep个三步这种组合, 共有多少种上楼方法
total += d;
}
}
}
}
cout << total << endl;
return 0;
}
输入: 10
输出: 274
这题做的很纠结, 我到现在也不知道是我错了, 还是答案错了, 我仔细的检查了我的代码, 没发现什么问题. 测试1, 输出1; 测试2, 输出2; 测试3, 输出4; 测试4, 输出7; 测试5, 输出13...用列举法一个个列下来发现这几个都是正确的...有空帮我看看哈:-)
在下午5点的时候我说了一句不该说的话, 做完3题去吃晚饭, 结果写完博客就到了现在...
