算法-枚 举
信息在计算机之间的演示
- 计算机的电路由逻辑门电路组成。一个逻辑门电路可以看成一个开关，每个开关的状态是“开"(高电位)或“关”(低电位)，即对应于或0
- 二进制数的一位，取值只能是0或1，称为一个“比特”(bit)，简写:b
- 八个二进制位称为一个“字节”(byte),简写:B
- 1024(2的10次方)字节称为1KB，1024KB称作1MB(1兆)，1024MB称作1GB，1024GB
- 0和1足以表示和传播各种信息。
由8个0essess 0或者1的组成的串，一共有28即256种不同的组合，这就足以表示10个阿拉伯数字以及英语中用到的所有字母和标点符号了。此即为ASCI1编码方案 - 图片、视频和可执行程序，也可以用0和1表示
数就是数，没有进制之分，只有数的表示形式，才有进制之分所谓“干进制数”，是“数的十进制表示形式"的简称。
1 2 4 8
0001 0010 0100 1000
eg：15=8+4+2+1 1111 7=4+2+1=111 5=4+1=101 21=8+8+4+1=10011
枚举
基于逐个尝试答案的一种问题求解策略
完美立方
形如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值小的先输出。
解题
四重循环枚举a,b,c,d ，a在最外层，d在最里层，每一层都是从小到大枚举，
a枚举范围[2,N],
b枚举范围[2,a-1],
c枚举范围[2,b-1],
d枚举范围[2,c-1]
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int N;
scanf("%d",&N);
for(int a=2;a<N;++a)
for (int b = 2; b<a; ++b)
for (int c = b; c<a; ++c)
for (int d = c; d < a; ++d)
if (a*a*a==b*b*b+c*c*c+d*d*d)
printf("Cube=%d,Triple=(%d,%d,%d)\n",a,b,c,d);
return 0;
}
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)
生理周期
人有体力、情商、智商的高峰日子，它们分别每隔 23天、28天和33天出现一次。对于每个人，我们想 知道何时三个高峰落在同一天。给定三个高峰出现 的日子p,e和i（不一定是第一次高峰出现的日子）, 再给定另一个指定的日子d，你的任务是输出日子d 之后，下一次三个高峰落在同一天的日子（用距离d 的天数表示）。例如：给定日子为10，下次出现三 个高峰同一天的日子是12，则输出2。
输入
输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力 高峰出现的日子。d是给定的日子，可能小于p, e或i。所有给 定日子是非负的并且小于或等于365，所求的日子小于或等于 21252。
输出
从给定日子起，下一次三个高峰同一天的日子（距离给定日子 的天数）。
解题
从d+1天开始，一直试到第21252 天，对其中每个日期k,看 是否满足,
(k – p)%23 == 0 && (k – e)%28 == 0 && (k-i)%33 == 0
#include <iostream>
#include <cstdio>
using namespace std;
#define N 21252
int main() {
int p,e,i,d,caseN0=0;
while (cin>>p>>e>>i>>d && p!=-1) {
++ caseN0;
int k;
for (k=d+1; (k-p)%23; ++k);
for (;(k-e)%28; k+=23);
for (;(k-i)%33; k+= 28*23);
cout<<"Case "<<caseN0<<":the next triple peak occurs in"<<k-d<<" days"<<endl;
}return 0;
}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 -1Case 1:the next triple peak occurs in21252 days
Case 2:the next triple peak occurs in21152 days
Case 3:the next triple peak occurs in19575 days
Case 4:the next triple peak occurs in16994 days
Case 5:the next triple peak occurs in8910 days
假币问题
有12枚硬币。其中有11枚真币和1枚假币。假币和真 币重量不同，但不知道假币比真币轻还是重。现在， 用一架天平称了这些币三次，告诉你称的结果，请你 找出假币并且确定假币是轻是重（数据保证一定能找 出来）。
输入
第一行是测试数据组数。 每组数据有三行，每行表示一次称量的结果。银币标号为 A-L。每次称量的结果用三个以空格隔开的字符串表示： 天平左边放置的硬币天平右边放置的硬币平衡状态。其 中平衡状态用``up'', ``down'', 或 ``even''表示, 分别为右 端高、右端低和平衡。天平左右的硬币数总是相等的。
输出
输出哪一个标号的银币是假币，并说明它比真币轻还是重。
解题对于每一枚硬币先假设它是轻的，看这样是否符合称 量结果。如果符合，问题即解决。如果不符合，就假 设它是重的，看是否符合称量结果。把所有硬币都试 一遍，一定能找到特殊硬币
#include <iostream>
#include <cstring>
using namespace std;
char Left[3][7]; //天平左边硬币
char Right[3][7]; //天平右边硬币
char result[3][7]; //结果
bool IsFake(char c,bool light) {
//light 为真表示假设假币为轻，否则表示假设假币为重
for(int i = 0;i < 3; ++i) {
char * pLeft,*pRight; //指向天平两边的字符串
if(light) {
pLeft = Left[i];
pRight = Right[i];
}
else {//如果假设假币是重的，则把称量结果左右对换
pLeft = Right[i];
pRight = Left[i];
}
switch(result[i][0]) { //天平右边的情况
case 'u':
if ( strchr(pRight,c) == NULL)
return false;
break;
case 'e':
if( strchr(pLeft,c) || strchr(pRight,c))
return false;
break;
case 'd':
if ( strchr(pLeft,c) == NULL)
return false;
break;
}
}
return true;
}
int main() {
int t;
cin >> t;
while(t--) {
for(int i = 0;i < 3; ++i) cin >> Left[i] >> Right[i] >> result[i];
for(char c='A'; c<='L';c++) {
if( IsFake(c,true) ){
cout << c << " is the counterfeit coin and it is light.\n";
break;
}
else if( IsFake(c,false) ){
cout << c << " is the counterfeit coin and it is heavy.\n";
break;
}
}
}
return 0; }
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
K is the counterfeit coin and it is light.