【hdoj 1005】有限狀態(tài)機
來源：程序員人生 發(fā)布時間：2015-08-18 08:30:03 閱讀次數(shù)：3368次
題目：傳送門
解答：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7
乍看之下像是遞歸。但是數(shù)據(jù)范圍太大了，1定會超時。可以想到找規(guī)律。
如果將 f(n) 視為1個狀態(tài)，那末決定它的是誰？是前兩個狀態(tài)。而且由于 mod 7，所以這個函數(shù)的定義域、值域都是{0,1,2,3,4,5,6}。
這樣，我們可以構造1個 7*7的有限狀態(tài)機（2維數(shù)組），每一個狀態(tài)填寫出現(xiàn)的次數(shù)。當我們行將填寫1個狀態(tài)時發(fā)現(xiàn)里面已出現(xiàn)了次數(shù)，當前次數(shù) - 已有次數(shù)就是循環(huán)的范圍。最多計算49次，我們1定會發(fā)現(xiàn)循環(huán)規(guī)律。
這里需要注意的是：
- 需要將輸入的 n 減去剛剛發(fā)現(xiàn)規(guī)律時的狀態(tài)機次數(shù)（正式開始循環(huán)），再對循環(huán)范圍取模；
- 當取模 = 0時，應當加上循環(huán)范圍。例如：1 1 4 2 4 2，如果直接依照取模計算，則 f(4) = 1 而不是 2；
- 無需判斷 n 是不是小于循環(huán)范圍，由于有限狀態(tài)機1定停機。即便小于對循環(huán)范圍取模仍得到自己。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
int a, b, i, j;
long n;
int map[7][7];
while (cin>>a>>b>>n && a && b && n)
{
if(n == 1 || n == 2)
{
cout<<"1"<<endl;
continue;
}
memset(map, 0, sizeof(map));
int val = 1;
map[1][1] = val;
i = 1;
j = (a*1 + b*1) % 7;
int k = 0;
while(!map[i][j])
{
val++;
map[i][j] = val;
int tmp = j;
j = (a*j + b*i) % 7;
i = tmp;
// 過剩操作，狀態(tài)機1定會停機
//num--;
//if (num == 0)
//{
// cout<<j<<endl;
// break;
//}
}
int circle = (val + 1) - map[i][j];
int start = map[i][j];
n = (n - (start - 1)) % circle;;
if(n == 0) n = circle;
n = n + (start - 1);
int ans;
for (int k = 0; k < 7; k++)
{
for (int l = 0; l < 7; l++)
{
if (n == map[k][l])
{
ans = k;
}
}
}
cout<<ans<<endl;
continue;
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
