算法篇-枚举_枚举算法生活实例

枚举

一、算法思想

枚举：即对可能的解集合一一列举。

枚举算法的实现往往通过使用循环（嵌套）就能够轻易实现，所以并没有什么思维难度。

解题思路：

1. 对解的每个参数的数据范围采用循环语句一一枚举，对每次枚举采用if语句判断是否是解以及是否是最优解。

枚举小技巧：

1. 有时候，我们枚举的东西如果满足一个公式，我们的循环可以少写一层，优化效率。比如如果枚举A+B+C=100，我们只需要枚举A和B，C可以直接用100-A-B，这样就少一层循环。

2. 当然，改变枚举的顺序也是一种小技巧。一般都是从小到大或者从大到小，但是还有其他顺序，这就用到了贪心算法。

3. 有时候我们需要枚举的是每个东西的状态（一般为两种状态），我们可以用二进制里面的0/1来表示这两种状态来进行枚举。比如（二进制枚举）有5个小朋友，枚举他们是否看过该博客，这时候可以把看过或者没有看过表示两种状态，分别用0和1表示。现在给数字5，二进制是101，说明第1和第3个小朋友看过。所以我们可以枚举0~（31）来表示5个小朋友每个小朋友之间的状态是什么。

4. 有时候，我们枚举的故率达不到题目所需，我们就可以将枚举出来的所有结果事先保存下来，然后在第二份程序里直接调用，这就是打表的思想。

5. 还有时候，简单的循环嵌套可能满足不了我们的需求，可以考虑递归算法实观。

二、完美立方问题

完美立方
题目描述
形如a3= b3 + c3 + d3的等式被称为完美立方等式。例如123= 63 + 83 + 103 。编写一个程序，对任给的正整数N (N≤100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 + c3 + d3，其中a,b,c,d 大于 1, 小于等于N，且b<=c<=d。

输入
一个正整数N (N≤100)。
输出
每行输出一个完美立方。输出格式为：
Cube = a, Triple = (b,c,d)
其中a,b,c,d所在位置分别用实际求出四元组值代入。

请按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则b值小的优先输出、仍相同则c值小的优先输出、再相同则d值小的先输出。
样例输入
24
样例输出
Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

总共有a，b，c，d四个变量，枚举就是一个个试，也就是说要试出四个变量至少要运用四个for循环叠加，最后判断a的立方是否等于b的立方加c的立方加d的立方，如果符合条件则输出a,b,c,d。

解题思路：

四层循环枚举a,b,c,d,a在最外层，d在最里层，每一层就是从小到大枚举

a枚举的范围[2,N], b枚举的范围[2, a-1],c枚举的范围[b, a-1]，d枚举的范围[c, a-1]

题解：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int N;
 8     cin >> N;
 9     //四层循环枚举a,b,c,d,a在最外层，d在最里层，每一层就是从小到大枚举
10     //a枚举的范围[2, N], b枚举的范围[2, a - 1], c枚举的范围[b, a - 1]，d枚举的范围[c, a - 1]
11     // 样例输出 Cube = 6, Triple = (3,4,5)
12     for (int a = 2; a <= N; a++)
13     {
14         for (int b = 2; b < a; b++)
15         {
16             for (int c = b; c < a; c++)
17             {
18                 for (int d = c; d < a; d++)
19                 {
20                     if (a * a * a == b * b * b + c * c * c + d * d * d)
21                     {
22                         cout << "Cube = " << a << " Triple = " << "(" << b << "," << c << "," << d << ")" << endl;
23                     }
24                 }
25             }
26         }
27     }
28     return 0;
29 }#include <iostream>
30 
31 using namespace std;
32 
33 int main()
34 {
35     int N;
36     cin >> N;
37     //四层循环枚举a,b,c,d,a在最外层，d在最里层，每一层就是从小到大枚举
38     //a枚举的范围[2, N], b枚举的范围[2, a - 1], c枚举的范围[b, a - 1]，d枚举的范围[c, a - 1]
39     // 样例输出 Cube = 6, Triple = (3,4,5)
40     for (int a = 2; a <= N; a++)
41     {
42         for (int b = 2; b < a; b++)
43         {
44             for (int c = b; c < a; c++)
45             {
46                 for (int d = c; d < a; d++)
47                 {
48                     if (a * a * a == b * b * b + c * c * c + d * d * d)
49                     {
50                         cout << "Cube = " << a << " Triple = " << "(" << b << "," << c << "," << d << ")" << endl;
51                     }
52                 }
53             }
54         }
55     }
56     return 0;
57 }

三、生理周期(生物节律)

人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为

每一个周期中有一天是高峰，在高峰这天，人会在相应的方面表现出色。

例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。

因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。

对于每个人，我们想知道何时三个高峰落在同一天。

对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。

你的任务是给定一个从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。

例如：给定时间为

输入格式

本题有多组数据。

对于每组数据，输入四个整数

当

输出格式

输出从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。

采用如下格式：

Case 1: the next triple peak occurs in 1234 days.

注意：即使结果是

数据范围

输入样例：

0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1

输出样例：

Case 1: the next triple peak occurs in 21252 days. Case 2: the next triple peak occurs in 21152 days. Case 3: the next triple peak occurs in 19575 days. Case 4: the next triple peak occurs in 16994 days. Case 5: the next triple peak occurs in 8910 days. Case 6: the next triple peak occurs in 10789 days.

解题思路：

从d+1天开始，一直试到第21252天，对其中每个日期k，看看是否满足 (k – p)%23 == 0 && (k – e) % 28==0&& (k – i) % 33 ==0

如何试的更快？ 跳着试

题解：

 1 #include <iostream>
 2 
 3 #define N 21252
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     /*
 9     从d+1天开始，一直试到第21252天，对其中每个日期k， 看看是否满足 (k - p)%23 == 0 && (k - e) % 28==0&& (k - i) % 33 ==0
10     如何试的更快？ 跳着试
11     Case 6: the next triple peak occurs in 10789 days.
12     */
13     int p, e, i, d, caseNo = 0;
14     while (cin >> p >> e >> i >> d && p != -1)
15     {
16         caseNo++;
17         int k;
18         for (k = d + 1; (k - p) % 23 != 0; k++);
19         for (; (k - e) % 28 != 0; k += 23);
20         for (; (k - i) % 33 != 0; k += 23 * 28);
21         cout << "Case " << caseNo << ": the next triple peak occurs in " << k - d << " days." << endl;
22     }
23     return 0;
24 }

四、假币问题（有bug）

萨莉·琼斯有一打旅行者银元硬币（一打指十二个）。

其中的十一个硬币是真币，还有一个是假币。

假币的颜色和大小与真币并无差别，但是重量上与真币不同。

遗憾的是，萨莉并不清楚假币是更重还是更轻。

幸好，她的朋友借给了她一个非常精准的天平。

朋友允许她进行三次称重，来找到假币的存在。

举例说明，如果她将两个硬币放置在天平两端，天平保持平衡，则说明两个硬币都是真的。

然后用一个真币和第三个硬币称重比较，如果天平不平衡，则确定第三个硬币是假币，并且根据天平的高低，也可判断假币是更轻还是更重。

通过合理安排，她确定可以通过三次称重找到假币的存在。

输入格式

共三行，每行描述一次称重。用大写字母 A~L 对

每行首先包含两个大写字母构成的字符串，分别表示左右两端的硬币（两端的硬币数量一定相同），然后包含一个单词 up，down 或 even，表示天平右端的倾斜程度。

输出格式

输出占一行，格式为 XX is the counterfeit coin and it is XXX.，其中 XX 是假币的字母编号，XXX 用来形容它更轻还是更重，更轻用 light 表示，更重 heavy 表示。

数据范围

保证一定有解。

输入样例：

1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

输出样例：

K is the counterfeit coin and it is light.

`解题思路：`

对于每一枚硬币先假设它是轻的，看这样是否符合称量结果。如果符合，问题即解决。如果不符合，就假设它是重的，看是否符合称量结果。把所有硬币都试一遍，一定能找到特殊硬币。

题解

 1 #include <iostream>
 2 #include <cstring> 
 3 
 4 using namespace std;
 5 
 6 char Left[3][7]; // 天平左边硬币
 7 char Right[3][7]; // 天平右边硬币
 8 char result[3][7]; // 结果
 9 bool IsFake(char c, bool  light);// light 为真表示假设假币为轻，否则表示假设假币为重
10 
11 
12 bool IsFake(char c, bool  light)// light 为真表示假设假币为轻，否则表示假设假币为重
13 {
14     for (int i = 0; i < 3; i++)
15     {
16         char* pLeft, * pRight;// 指向天平两边的字符串
17         if (light)
18         {
19             pLeft = Left[i];
20             pRight = Right[i];
21         }
22         else // 如果假设假币是重的， 则把称量结果左右互换
23         {
24             pLeft = Right[i];
25             pRight = Left[i];
26         }
27         switch (result[i][0])
28         {
29         case 'u':
30             if (strchr(pRight, c) == NULL)
31             {
32                 return false;
33             }
34             break;
35         case 'e':
36             if (strchr(pLeft, c) || strchr(pRight, c))
37             {
38                 return false;
39             }
40             break;
41         case 'd':
42             if (strchr(pLeft, c) == NULL)
43             {
44                 return false;
45             }
46             break;
47         }
48     }
49     return true;
50 }
51 
52 
53 int main()
54 {
55     int t;
56     cin >> t;
57     while (t--)
58     {
59         for (int i = 0; i < 3; i++)
60         {
61             cin >> Left[i] >> Right[i] >> result[i];
62 
63         }
64         for (char c = 'A'; c < 'L'; c++)
65         {
66             if (IsFake(c, true))
67             {
68                 cout << c << " is the counterfeit coin and it is light." << endl;
69                 break;
70             }
71             else if (IsFake(c, false))
72             {
73                 cout << c << " is the counterfeit coin and it is heavy." << endl;
74                 break;
75             }
76         }
77     }
78 
79     return 0;
80 }

今天的文章算法篇–枚举_枚举算法生活实例分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/54399.html

算法篇–枚举_枚举算法生活实例

枚举

一、算法思想

解题思路：

二、完美立方问题

解题思路：

题解：

三、生理周期(生物节律)

输入格式

输出格式

数据范围

输入样例：

输出样例：

解题思路：

题解：

四、假币问题（有bug）

输入格式

输出格式

数据范围

输入样例：

输出样例：

解题思路：

题解

相关推荐

发表回复

`解题思路：`