C++竞赛经典代码(2)
案例1 从小到大输出1-100
题目描述
从小输出1-100的自然数,每个数据独占一行。
解析:输出换行可以使用endl也可以使用”\n”。但是频繁输出数据时建议使用”\n”,因为每次输出endl时都有会刷新一次。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
for (int i = 1; i <= 100; i++)
{
cout << i << "\n";
}
return 0;
}
也可以用while循环来输出,参考代码如下:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i = 1;
while (i <= 100)
{
cout << i << "\n";
i++;
}
return 0;
}
对于一个循环其实包括4个部分:初始值、终止值、步长和循环体。也有循环三要素的提法:循环变量、循环体、终止条件。对于前面的for(;;)循环,”int i = 1″中的1就是循环的初始值,这里的变量i是用于控制循环的也称为循环变量;”i <= 100″中的100就是循环的终止值,这个逻辑表达式也称为循环的终止条件;i++的作用是每次增加1,这里的1就是循环的步长;而大括号里的内容是每次循环都要执行的代码,被称为循环体。
案例2 循环输入数据
题目描述
输入两个数,回车后输出结果,然后再输入一对,回车再输出结果… …
解析:通常来说输入多少对数据是有具体个数的,但有的时候需要在不确定具体数量的情况来输入数据,这里有固定的写法,参加竞赛的同学需要牢记。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
while(cin>>a>>b)
{
cout<<a+b<<endl;
}
return 0;
}
这种写法效率低,当数据量非常大的时候可能会时间超限,因此可以改成如下写法:
while (scanf("%d%d", &a, &b) != EOF)
或者:
while (~scanf("%d%d", &a, &b))
以上这两种写法都需要特殊的方法来结束循环。EOF(end of file)就是文件的结束,他相当于-1。通在windows下需要输入Ctrl+Z,然后回车就可以结束循环;在Unix、Mac OS、Linux系统下需要在新的一行输入Ctrl+D,然后回车来结束循环。
结束循环的条件是根据输入的数据值,比如当输入数据位0时结束循环,参考代码如下:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
while (cin >> a >> b)
{
if (a == 0)
break;
cout << a + b << endl;
}
return 0;
}
有的时候是根据输入数据的个数来结束循环。比如最后一行输入一个数据,代表结束循环。参考代码如下:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b;
while (scanf("%d%d", &a, &b) == 2)
{
cout << a + b << endl;
}
return 0;
}
案例3 循环求和
题目描述
求自然数的前n项和,即1+2+3+…+n的和。
解析:当然这种数列求和最简单的方式是高斯求和,即S = n*(n+1)/2。这里就练习用循环来求和的方法。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, sum = 0;
cin >> n;
for (int i = 1; i <= n; i++)
sum += i;
cout << sum << endl;
return 0;
}
案例4 求台阶数量
题目描述
一次爱因斯坦给他朋友出了这样一道数学题:一条长长的台阶,如果每部走2台阶,最后剩1阶;每步3台阶,最后剩2阶;每步5台阶,最后剩4阶;每步6台阶,最后剩5阶;只有每步7台阶,才刚好一节不剩走完.请问,有多少台阶?
解析:从数学的角度看,如果多加一阶,那么每步走2,3,4,5,6就都能走完,所以台阶数+1是2,3,4,5,6的最小公倍数的整数倍。即是60的整数倍。台阶数就是60*(k-1),因为60*(k-1)是7的整数倍,所以k=2,9,16,23。所以台阶数就是119,539,959。台阶最少就是119阶。从计算思维的角度看,我们可以用循环的方式枚举各种可能性,满足所有的要求后退出即可。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i = 0;
while (1)
{
if (i % 2 == 1 && i % 3 == 2 && i % 5 == 4 && i % 6 == 5 && i % 7 == 0)
break;
i++;
}
cout << i << endl;
return 0;
}
while(1)的写法是一个死循环(Infinite Loop),用for写死循环的方式为:for( ; ; )。可以按 Ctrl + C 键终止一个无限循环。
案例5 落地次数
题目描述
小球从100米高处自由落下,着地后又弹回高度的一半再落下。经过多少次落地后,小球弹起的高度才会低于0.5米?
解析:通过循环模拟小球落地的过程即可。
参考代码:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int cnt = 0;
double h = 100.0;
while (h > 0.5)
{
cnt++;
h /= 2;
}
cout << cnt << endl;
return 0;
}
用for循环写也一样:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int cnt = 0;
for (double h = 100.0; h > 0.5; h /= 2)
{
cnt++;
}
cout << cnt << endl;
return 0;
}
案例6 判断质数
题目描述
输入一个整数n,如果是质数则输出yes,否则输出no。
解析:质数是指除了1和本身之外没有其他约数的数。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
bool isPrime = true;
cin >> n;
if (n <= 1)
isPrime = false; //特殊情况单独处理
for (int i = 2; i <= sqrt(n); i++)
if (n % i == 0)
{
isPrime = false;
break;
}
if (isPrime)
cout << "yes";
else
cout << "no";
cout << endl;
return 0;
}
案例7 斐波那契额数列第n项
题目描述
斐波那契数列的递推公式为:F(1) = 1, F(2) = 1, F(n) = F(n – 1) + F(n – 2) (n ≥ 3, n ∈ N*)。这个公式定义了如何从已知的项推导出下一个项。
解析:斐波那契数列有很多种求法,比如递归、一维数组等方法,这里使用循环来求解。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b, c;
int n;
cin >> n;
if (n <= 2)
{
cout << 1 << endl;
return 0;
}
a = 1, b = 1;
for (int i = 3; i <= n; i++)
{
c = a + b;
a = b, b = c;
}
cout << c << endl;
return 0;
}
案例8 求最大公约数
题目描述
输入两个整数,输出这两个数的最大公约数。
解析:求最大公约数常用的方法有欧几里得算法和更相减损术。这两种方法的数学原理都是同余定理,有兴趣的同学可以学习一下。另外还需要知道最大公约数乘以最小公倍数等于两个数的乘积。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a, b, r = 0;
cin >> a >> b;
while (b != 0)
{
r = a % b;
a = b;
b = r;
}
cout << a << endl;
return 0;
}
