?? 1527 取石子游戲.cpp
字號:
/*
先找規律,算幾個很小的必敗狀態
1,2
3,5
4,7
6,10
8,13
...
發現所有的數恰在序列中出現一次
而且差為1,2,3,4,5,...
所以這兩個序列構成正整數集的一個分劃,猜想可以由betty定理生成(僅僅是猜想,不需要
太多的理由^_^)
其實,這兩個序列恰好對應betty定理中alpha=(1+sqrt(5))/2,beta=(3+sqrt(5))/2的情況,
所以問題解決。
這題不算出公式的話是沒法做的,因為規模太大,必敗狀態太多,沒有任何的辦法
betty定理是說,如果無理數alpha和beta滿足
1.alpha,beta>0
2.1/alpha+1/beta=1
那么,序列{[alpha*n]}和{[beta*n]}構成自然數集的一個分劃,其中[]是取整函數
這道題對應的alpha和beta分別是(1+sqrt(5))/2,(3+sqrt(5))/2
所以alpha=1/黃金分割
beta/alpha=黃金分割
可以說跟黃金分割有關,但也只是一種巧合吧,黃金分割還是經常出現的
*/
#include <cstdio>
#include <cmath>
using namespace std;
double a = (1.0 + sqrt(5.0)) / 2.0;
double b = (3.0 + sqrt(5.0)) / 2.0;
int main()
{
int big, small, n, t1, t2,t;
while(scanf("%d %d",&big,&small)==2)
{
if(big < small)
{
t=big;
big=small;
small=t;
}
n = ceil(big / b);
t1 = a * n;
t2 = b * n;
if(small == t1 && big == t2)
printf("0\n");
else printf("1\n");
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -