完美立方：
- 形如 a^3 = b^3 + c^3 + d^3 的等式稱為完美立方式依疼。編寫一個(gè)程序，對任何給定的正整數(shù)N(N<=100)而芥，尋找所有的四元組(a,b,c,d)使得a^3 = b^3 + c^3 + d^3律罢，其中a,b,c,d大于1，小于等于N棍丐，且b<=c<=d.
- 輸入：一個(gè)正整數(shù)N(N<=100)
- 輸出：每行輸出一個(gè)完美立方误辑。輸出格式為：
Cube = a, Triple = (b,c,d)
按照a的值從小到大依次輸出。當(dāng)a的值相同時(shí)歌逢，b值小的優(yōu)先輸出...
- 樣例輸入：
- 樣例輸出：
- 解題思路：四重循環(huán)枚舉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天出現(xiàn)一次讨惩。給定三個(gè)高峰出現(xiàn)的日子p,e,i辟癌，再給定另一個(gè)指定的日子d,輸出日子d后下一個(gè)三高峰出現(xiàn)的日子(用距離d的天數(shù)表示)。
- 解題思路：從d+1天開始荐捻，一直試到第21252天(232833=21252),對其中的每個(gè)日期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作為各個(gè)硬幣的代號(hào)厂置，假幣可能比真幣略輕，也可能略重魂角，現(xiàn)在利用天枰昵济，根據(jù)輸入的3次稱量，找出假幣野揪，并輸出假幣是輕還是重（數(shù)據(jù)保證一定能找出來）
- 輸入：第一行為用例組數(shù)T访忿，每組用例占三行每行表示一次稱量結(jié)果，一次稱量結(jié)果由三個(gè)字符串組成斯稳，前兩個(gè)字符串等長表示放在天秤兩邊的硬幣編號(hào)海铆，第三個(gè)字符串表示稱量結(jié)果，even表示平衡挣惰，up表示左端略高卧斟，down表示左邊略低（以右側(cè)為標(biāo)準(zhǔn)，up表示右側(cè)高）
- 輸出：對于每組用例憎茂，輸出假幣編號(hào)并判斷其是輕還是重
- 解題思路：對于每一枚硬幣唆涝，先假設(shè)它是假幣且輕，如果符合唇辨，問題即解決廊酣。否則假設(shè)它是假幣且重，看是否符合稱量結(jié)果赏枚。把所有硬幣都假設(shè)一遍亡驰，一定能找出假幣。
#include <iostream>
#include <cstring>
char Left[3][7];//天平左側(cè)硬幣饿幅，一共有12個(gè)硬幣凡辱，稱量的時(shí)候一邊放6個(gè)，三次稱量栗恩，所以數(shù)組開[3][7].
char Right[3][7];//天平右側(cè)硬幣
char result[3][7];//三次稱量結(jié)果
bool isFake(char c,bool light);//假設(shè)硬幣c是假幣透乾，light==true時(shí)假設(shè)它為輕，light==false時(shí)假設(shè)為重，返回值為true表示假設(shè)成立
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;
}
//下面這個(gè)函數(shù)很重要乳乌，是本題的核心
bool isFake(char c,bool light)
{
//light==true假設(shè)假幣為輕捧韵，否則假設(shè)假幣為重
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];
}
//假設(shè)假幣為輕
switch(result[i][0])
{
case 'u':
if(strchr(pright,c)==NULL) //右側(cè)up，右側(cè)輕汉操，輕假幣在右側(cè)再来。通過調(diào)用strchr判斷char c是否在pright里
return false;
break;
case 'e':
if(strchr(pright,c) || strchr(pright,c)) //兩邊相平，兩側(cè)都沒有假幣
return false;
break;
case 'd':
if(strchr(pleft,c)==NULL) //右側(cè)下沉磷瘤，輕假幣在左側(cè)
return false;
break;
}
}
return true;
}
熄燈問題：
- 問題描述：有一個(gè)由按鈕組成的矩陣芒篷，5行6列，每個(gè)按鈕的位置上有一盞燈采缚，當(dāng)按下一個(gè)按鈕時(shí)针炉，該按鈕以及周圍位置（上下左右）燈的狀態(tài)都會(huì)改變。給定矩陣中每盞燈的初始狀態(tài)扳抽，求一種按鈕方案篡帕，使得所有的燈都熄滅。
- 問題分析：第二次按下一個(gè)按鈕時(shí)摔蓝，將抵消第一次按下時(shí)產(chǎn)生的結(jié)果赂苗，所以一個(gè)按鈕最多只需要按一次。
- 第一想法是通過枚舉所有可能的按鈕狀態(tài)贮尉，對每個(gè)狀態(tài)計(jì)算一下最后燈的情況拌滋，看是否都熄滅。但是30個(gè)開關(guān)有2的30次方種狀態(tài)猜谚，程序會(huì)運(yùn)超時(shí)败砂。
- 枚舉局部
#include <iostream>
#include <string>
#include <cstring>
#include <memory>
using namespace std;
char oriLights[5];//原始燈亮滅情況
char lights[5];// 運(yùn)行時(shí)燈亮滅情況
char result[5];//存放按開關(guān)的情況
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)//枚舉第一行按開關(guā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)//改變同行燈狀態(tài)
{
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;//改變下一列燈狀態(tài)
switchs=lights[i]; //下一行按開關(guān)取決于這一行燈的亮滅情況，如果本行某一列燈亮魏铅，就要在下一行按相同列的開關(guān)讓它熄滅
}
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;
}
}
