算法篇--枚举

标签：输出 Cube -- 算法 days int 枚举 Triple

枚举

一、算法思想

二、完美立方问题

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

四、假币问题

一、算法思想

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

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

解题思路：

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 }

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

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

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

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

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

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

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

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

例如：给定时间为 1010，下次出现三个高峰同天的时间是 1212，则输出 22（注意这里不是 33）。

输入格式

本题有多组数据。

对于每组数据，输入四个整数 p,e,i,dp,e,i,d。其中，p,e,ip,e,i 分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。dd 是给定的时间，可能小于 p,ep,e 或 ii。

当 p=e=i=d=−1p=e=i=d=−1 时，输入数据结束。

输出格式

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

采用如下格式：

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

注意：即使结果是 11 天，也使用复数形式 days。

数据范围

0≤p,e,i,d<3650≤p,e,i,d<365，
数据保证答案一定小于 21252

输入样例：

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 }

四、假币问题

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

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

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

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

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

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

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

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

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

输入格式

共三行，每行描述一次称重。用大写字母 A∼LA∼L 对 1212 个硬币分别标号，用天平右端的倾斜程度来描述称重结果。

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

输出格式

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

数据范围

保证一定有解。

输入样例：

ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even

输出样例：

K is the counterfeit coin and it is light.

标签：输出,Cube,--,算法,days,int,枚举,Triple
From： https://www.cnblogs.com/Gaowaly/p/16988439.html

枚举

一、算法思想

解题思路：

二、完美立方问题

解题思路：

题解：

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

输入格式

输出格式

数据范围

输入样例：

输出样例：

解题思路：

题解：

四、假币问题

输入格式

输出格式

数据范围

输入样例：

输出样例：

相关文章

赞助商

阅读排行