首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 其他教程 > 其他相关 >

屉子原理

2012-11-26 
抽屉原理在做题时,犯的错误:把f1,f2这些比较特殊的,可能形不成周期的数字放到抽屉数组当中去,自然会引起错

抽屉原理

在做题时,犯的错误:

把f1,f2这些比较特殊的值,可能形不成周期的数字放到抽屉数组当中去,自然会引起错误:

例如:

屉子原理

如果把f1=1,f2=1也写到arr中去,当用例为14 14 14时,明显arr数组里面存的是1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0……

显然,从arr的第一位开始找起,找不到周期,那么周期dis就会没有或者沿用上一个用例的,都会出错。

如果f1,f2不存进去,最后在算dis的时候注意,减少了3而不是1:

dis = (n - 3) % dis;
//runtime error
#include<iostream>using namespace std;int main(){int a,b,n;int f1;int f2;int arr[65];int dis;while(cin>>a>>b>>n){f1 = 1;f2 = 1;if((a == 0)&&(b == 0)&&(n == 0)){return 0;}for(int i=0; i<65; i++){arr[i] = (a*f2 + b*f1)%7;f1 = f2;f2 = arr[i];}for(int i=1; i<60; i++){if((arr[i] == arr[0])&&(arr[i+1] == arr[1])){dis = i;break;}}dis = (n - 3) % dis;cout<<arr[dis]<<endl;}return 0;} 


热点排行