【hdoj 1005】有限状态机
发布时间：2020-12-13 20:47:01 所属栏目：PHP教程 来源：网络整理
导读：题目： 传送门 解答： f(1) = 1,f(2) = 1,f(n) = (A * f(n - 1) B * f(n - 2)) mod 7 乍看之下像是递归。但是数据范围太大了，1定会超时。可以想到找规律。 如果将 f(n) 视为1个状态，那末决定它的是谁？是前两个状态。而且由于 mod 7，所以这个函数的定义域
|
题目：传送门 解答：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定会发现循环规律。 这里需要注意的是：
#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,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;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |