算法竞赛入门经典（第2版）第2章
发布时间
阅读量：
阅读量
习题2-2 韩信点兵（hanxin）
据说韩信智谋超群，并未直接清点军队的人数。相反地，他只需让士兵们依次以三人一组、五人一组以及七人一组地变换队形即可。每当他观察队伍的最后一列时就能迅速得出总兵力的数量。每组测试用例由三个非负整数组成a, b, c（其中 a<3, b<5, c<7），请计算并返回满足条件的最小总人数（若无解，则提示无解）。已知所有可能情况下的总人数均在10到100之间（含端点）。当数据读取完毕后会自动终止处理，请给出所有结果。
#include <iostream>
int main()
{
using std::cin;
using std::cout;
using std::endl;
int a[2], b[2], c[2];
for (int i = 0; i < 2; i++)
{
cin >> a[i] >> b[i] >> c[i];
}
for (int i = 0; i < 2; i++)
{
int n = 10;
while (n >= 10 && n <= 100)
{
if (n % 3 == a[i] && n % 5 == b[i] && n % 7 == c[i])
{
break;
}
n++;
}
if (n > 100)
cout << "Case " << i+1 << ": " << "No answer" << endl;
else
cout << "Case " << i+1 << ": " << n << endl;
}
getchar();
getchar();
return 0;
}习题2-2 子序列的和（subsequence）
给定两个满足条件的正整数n和m（其中n小于m且均小于等于1e6），计算并输出从1/n²开始直到1/m²的平方倒数之和，并保留五位小数结果。程序接受多组测试数据作为输入，并在遇到n等于m等于零时程序终止运行。请注意题目中的陷阱设置。
#include<iostream>
#include<iomanip>
using namespace std;
int main(void)
{
int n, m;
while (cin >> n >> m)
{
if (m == 0 && n == 0)
{
break;
}
double sum = 0;
int i;
int kase = 1;
for (i = 0; i <= m - n; i++)
{
sum += 1.0 / (i + n) * 1.0 / (i + n);
}
cout << "case " << kase << ": " << setprecision(5) << fixed << sum << endl;
kase;
}
}陷阱就是在n特别大时如果直接n*n就会溢出，所以只能连除两次
习题2-6 排列（permulation）
使用数字1至9生成三个三位数分别为abc、def和ghi，并且每个数字仅使用一次。要求这三个数的比例为1:2:3，请以'abc def ghi'的形式列出所有满足条件的组合。提示：无需过多思考
#include<iostream>
using namespace std;
int main(void)
{
int abc, def, ghi;
int count = 0;
int *p = new int [10];
memset(p, 0, 10*sizeof(*p));
for (abc = 123; abc < 329; abc++)
{
def = 2 * abc;
ghi = 3 * abc;
p[abc / 100] = 1;
p[abc / 10 % 10] = 1;
p[abc % 10] = 1;
p[def / 100] = 1;
p[def / 10 % 10] = 1;
p[def % 10] = 1;
p[ghi / 100] = 1;
p[ghi / 10 % 10] = 1;
p[ghi % 10] = 1;
for (int i = 1; i < 10; i++)
count += p[i];
if (count == 9)
{
cout << abc << " " << def << " " << ghi << endl;
}
memset(p, 0, 10*sizeof(*p));
count = 0;
}
delete[] p;
cin.get();
}全部评论 (0)
还没有任何评论哟~