完美立方：
- 形如 a^3 = b^3 + c^3 + d^3 的等式称为完美立方式。编写一个程序，对任何给定的正整数N(N<=100)，寻找所有的四元组(a,b,c,d)使得a^3 = b^3 + c^3 + d^3，其中a,b,c,d大于1，小于等于N，且b<=c<=d.
- 输入：一个正整数N(N<=100)
- 输出：每行输出一个完美立方。输出格式为：
Cube = a, Triple = (b,c,d)
按照a的值从小到大依次输出。当a的值相同时，b值小的优先输出...
- 样例输入：
- 样例输出：
- 解题思路：四重循环枚举a,b,c,d。a在最外层，d在最里层。每一层都是从小到大枚举。
- a枚举范围：[2,N], b枚举范围：[2,a-1],c枚举范围：[b,a-1],d枚举范围：[c,a-1]
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
int N;
cin>>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)
{
cout<<"Cube = "<<a<<",";
cout<<"Triple = ("<<b<<","<<c<<","<<d<<")"<<endl;
}
}
}
}
}
return 0;
}
生理周期：
- 问题描述：人有体力、智力和情商高峰的日子，它们分别每隔23，28，33天出现一次。给定三个高峰出现的日子p,e,i，再给定另一个指定的日子d,输出日子d后下一个三高峰出现的日子(用距离d的天数表示)。
- 解题思路：从d+1天开始，一直试到第21252天(232833=21252),对其中的每个日期K查看是否满足(k-p)%23==0 &&(k-e)%28==0 &&(k-i)%33==0
- 跳着试
#include <iostream>
using namespace std;
#define N 21252
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
int p,e,i,d,caseNo=0;
while(cin>>p>>e>>i>>d &&p!=-1)
{
++caseNo;
int k;
for(k=d+1;(k-p)%23;++k);
for(;(k-e)%28;k+=23);
for(;(k-i)%33;k+=23*28);
cout<<"Case "<<caseNo<<
" :The next triple peek occurs in "<<k-d<<"days."<<endl;
}
return 0;
}
称硬币：
- 问题描述：有一打（12枚）硬币，其中有且仅有1枚假币，11枚真币，用A~L作为各个硬币的代号，假币可能比真币略轻，也可能略重，现在利用天枰，根据输入的3次称量，找出假币，并输出假币是轻还是重（数据保证一定能找出来）
- 输入：第一行为用例组数T，每组用例占三行每行表示一次称量结果，一次称量结果由三个字符串组成，前两个字符串等长表示放在天秤两边的硬币编号，第三个字符串表示称量结果，even表示平衡，up表示左端略高，down表示左边略低（以右侧为标准，up表示右侧高）
- 输出：对于每组用例，输出假币编号并判断其是轻还是重
- 解题思路：对于每一枚硬币，先假设它是假币且轻，如果符合，问题即解决。否则假设它是假币且重，看是否符合称量结果。把所有硬币都假设一遍，一定能找出假币。
#include <iostream>
#include <cstring>
char Left[3][7];//天平左侧硬币，一共有12个硬币，称量的时候一边放6个，三次称量，所以数组开[3][7].
char Right[3][7];//天平右侧硬币
char result[3][7];//三次称量结果
bool isFake(char c,bool light);//假设硬币c是假币，light==true时假设它为轻，light==false时假设为重，返回值为true表示假设成立
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
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++)//从'A'硬币到'L'硬币枚举
{
if(isFake(c,true))
{
cout<<c<<"is the counterfeit coin and it is light."<<endl;
break;
}
if(isFake(c,false))
{
cout<<c<<"is the counterfeit coin and it is heavy."<<endl;
break;
}
}
}
return 0;
}
//下面这个函数很重要，是本题的核心
bool isFake(char c,bool light)
{
//light==true假设假币为轻，否则假设假币为重
for(int i=0;i<3;++i)
{
char* pleft; //指向天平两边的字符串
char* 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) //右侧up，右侧轻，轻假币在右侧。通过调用strchr判断char c是否在pright里
return false;
break;
case 'e':
if(strchr(pright,c) || strchr(pright,c)) //两边相平，两侧都没有假币
return false;
break;
case 'd':
if(strchr(pleft,c)==NULL) //右侧下沉，轻假币在左侧
return false;
break;
}
}
return true;
}
熄灯问题：
- 问题描述：有一个由按钮组成的矩阵，5行6列，每个按钮的位置上有一盏灯，当按下一个按钮时，该按钮以及周围位置（上下左右）灯的状态都会改变。给定矩阵中每盏灯的初始状态，求一种按钮方案，使得所有的灯都熄灭。
- 问题分析：第二次按下一个按钮时，将抵消第一次按下时产生的结果，所以一个按钮最多只需要按一次。
- 第一想法是通过枚举所有可能的按钮状态，对每个状态计算一下最后灯的情况，看是否都熄灭。但是30个开关有2的30次方种状态，程序会运超时。
- 枚举局部
#include <iostream>
#include <string>
#include <cstring>
#include <memory>
using namespace std;
char oriLights[5];//原始灯亮灭情况
char lights[5];// 运行时灯亮灭情况
char result[5];//存放按开关的情况
int getBit(char c,int i);
void setBit(char &c,int i,int v);
void flipBit(char& c,int i);
void printResult(int i,char result[]);
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int main(int argc, char** argv) {
int T;
cin>>T;
for(int t=1;t<=T;++t)
{
for(int i=0;i<5;++i)
{
for(int j=0;j<6;++j)
{
int s;
cin>>s;
setBit(oriLights[i],j,s);
}
}
for(int n=0;n<64;++n)//枚举第一行按开关情况000000~111111
{
int switchs=n;
memcpy(lights,oriLights,sizeof(oriLights));
for(int i=0;i<5;++i)
{
result[i]=switchs;
for(int j=0;j<6;++j)//改变同行灯状态
{
if(getBit(switchs,j))
{
if(j>0)flipBit(lights[i],j-1);
flipBit(lights[i],j);
if(j<5)flipBit(lights[i],j+1);
}
}
lights[i+1]^=switchs;//改变下一列灯状态
switchs=lights[i]; //下一行按开关取决于这一行灯的亮灭情况，如果本行某一列灯亮，就要在下一行按相同列的开关让它熄灭
}
if(lights[4]==0)
{
printResult(t,result);
break;
}
}
}
return 0;
}
int getBit(char c,int i)
{
return (c>>i)&1;
}
void setBit(char &c,int i,int v)
{
if(v)
{
c |= (1<<i);
}
else
{
c &= ~(1<<i);
}
}
void flipBit(char& c,int i)
{
c ^= (1<<i);
}
void printResult(int i,char result[])
{
cout<<"PUZZLE #"<<endl;
for(int i=0;i<5;++i)
{
for(int j=0;j<6;++j)
{
cout<<getBit(result[i],j);
if(j<5)cout<<" ";
}
cout<<endl;
}
}
