【SEU程序设计课笔记】 Mooc - Chapter 5 - 质因数分解存款方案完全数

it2025-11-14 10

Mooc 课程：程序设计基础——发现计算之美李骏扬、魏海坤、仰燕兰、朱蔚萍、杨万扣网址：https://www.icourse163.org/course/SEU-1003771004

质因数分解

见我的博客【C++ 程序】质因数分解。

存款方案

假设银行整存整取存款不同期限的月利率为：

0.63% 期限为1年0.66% 期限为2年0.69% 期限为3年0.75% 期限为5年0.84% 期限为8年现在已知某人手上有2000元，要求通过计算选择一种存钱方案，使得这笔钱存入银行20年后获得的利息最多。假定银行对超出存款期限的那部分时间不付利息；在一个期限内，不采用复利，但是如果一个期限结束，则连本带息进入下一个定期周期，例如，一个2年期，利息为

2000 \times (1+0.66\% \times 2)

，连存两个1年期，利息为

2000 \times (1+0.63\%) \times (1+0.63\%)

。

觉得题目有些矛盾。前面是说月息，而后面示例却是当作年的。（此处用年利率计算）先给出一种麻烦的却又借鉴价值的方法：（此题其实和顺序无关，而这个代码是考虑顺序的）

#include <iostream> #include <cmath> #include <vector> using namespace std; double money = 2000; double max_money = 2000; // 最大获益的金额 unsigned year = 0; // 已存年数 // 显然多存一年无息不如多存一年期，故不考虑该情况。 string choice[] = { "一年期","两年期","三年期","五年期","八年期" }; vector<string> max_choice; size_t i[20]; // 最多存20次 // 先定义到期时总利率。 double a[] = { 1 + 0.63 / 100 * 1, // 一年期 1 + 0.66 / 100 * 2, // 两年期 1 + 0.69 / 100 * 3, // 三年期 1 + 0.75 / 100 * 5, // 五年期 1 + 0.84 / 100 * 8 // 八年期 }; // 定义存款时间 unsigned b[] = { 1,2,3,5,8 }; void choose(unsigned n,int t) { for (i[t] = 0; i[t] != 5; i[t]++) { if (n + b[i[t]] == 20) // 已经存满20年了 { money *= a[i[t]]; if (money > max_money) // 判断是否为更佳的解法 { max_money = money; max_choice.clear(); for (size_t j = 0; j <= t; j++) max_choice.push_back(choice[i[j]]); money = 2000; // 恢复状态 } else money = 2000; } else if (n + b[i[t]] < 20) { money *= a[i[t]]; choose(n + b[i[t]], t + 1); } else money = 2000; } } int main() { choose(0, 0); cout << "最佳方案为："; for (auto c : max_choice) cout << c << "，"; cout << "获利" << max_money - 2000 << "元。" << endl; return 0; }

Output: （其他简单方法读者可以自己思考一下）

完全数

完全数是一种所有因子（除了该数字本身之外）求和，等于该数字本身的数字。例如，6 的因子有：1、2、3、6，去掉 6，那么 $1 + 2 + 3 = 6$ ；又如，28 的因子有：1、2、4、7、14、28，除了28之外， $1 + 2 + 4 + 7 + 14 = 28$ 。完全数的另一种求法是：如果 $2^N-1)$ 是质数，那么 $2^{N-1}(2^N-1))$ 就是梅花数。请用两种方法，求正整数中前 5 个完全数。

Way I

#include <iostream> #include <cmath> using namespace std; int main() { unsigned cnt = 0; for (int i = 2; cnt != 5; i++) { unsigned sum = 1; // add 1 by default for (int j = 2; j <= sqrt(i); j++) sum += (i % j) ? 0 : (j * j == i) ? j : (j + i / j); if (sum == i) cout << "No." << ++cnt << ": " << i << endl; } return 0; }

慢死了，第五个半天出不来，就像这样：

Way II

#include <iostream> #include <cmath> using namespace std; int is_prime(unsigned n) // test whether it is a prime number { if (n == 1) return 0; for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return 0; return 1; } int main() { unsigned cnt = 0; for (int i = 1; cnt != 5; i++) if (is_prime(static_cast<unsigned>(pow(2, i)) - 1)) cout << "No." << ++cnt << ": " << static_cast<unsigned>(((pow(2, i)) - 1) * pow(2, i - 1)) << endl; return 0; }

Output:

Way III

看到群里积极的讨论，想搞一个方法一的优化，使用先因式分解再用数学公式，结果更慢了。

#include <iostream> #include <vector> #include <ctime> #include <cmath> using namespace std; vector<int> prime; int my_pow(int n1, int n2) { int ret = 1; for (int i = 0; i != n2; i++) ret *= n1; return ret; } bool test(int n) { int sigma = 1; int alr = 1; int cnt = 0; for (size_t i = 0; prime[i] <= n / alr; i++) { int state = 0; while (state == 0) // still this number { if (n / alr % prime[i] == 0) { cnt++; alr *= prime[i]; state = 0; if (sigma > 2 * n) return false; // can already be deduced as false } else { sigma *= (my_pow(prime[i], cnt + 1) - 1) / (prime[i] - 1); // using the formula cnt = 0; state = 1; } } } if (sigma == 2 * n) return true; else return false; } int main() { unsigned cnt = 0; for (int i = 2; cnt != 5; i++) { int index = 1; for (int j = 2; j * j <= i; j++) if (i % j == 0) { index = 0; break; } if (index == 1) prime.push_back(i); // it is a prime number, then it is false else if (test(i) == true) cout << "No." << ++cnt << ": " << i << endl; } cout << "\nTotal time: " << clock() / 1000 << " seconds." << endl; return 0; }

Output: 花了好几个小时才输出！