【hdoj 1005】有限狀態機
來源：程序員人生 發布時間：2015-08-18 08:30:03 閱讀次數：3374次
題目：傳送門
解答：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7
乍看之下像是遞歸。但是數據范圍太大了，1定會超時?？梢韵氲秸乙幝?。
如果將 f(n) 視為1個狀態，那末決定它的是誰？是前兩個狀態。而且由于 mod 7，所以這個函數的定義域、值域都是{0,1,2,3,4,5,6}。
這樣，我們可以構造1個 7*7的有限狀態機（2維數組），每一個狀態填寫出現的次數。當我們行將填寫1個狀態時發現里面已出現了次數，當前次數 - 已有次數就是循環的范圍。最多計算49次，我們1定會發現循環規律。
這里需要注意的是：
- 需要將輸入的 n 減去剛剛發現規律時的狀態機次數（正式開始循環），再對循環范圍取模；
- 當取模 = 0時，應當加上循環范圍。例如：1 1 4 2 4 2，如果直接依照取模計算，則 f(4) = 1 而不是 2；
- 無需判斷 n 是不是小于循環范圍，由于有限狀態機1定停機。即便小于對循環范圍取模仍得到自己。
#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;
// 過剩操作，狀態機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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
