杭电ACM刷题(2):1005,Number Sequence 标签: 杭电acmC语言 2017-05-11 22:43 116人阅读
Problem Description
A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
Output
For each test case, print the value of f(n) on a single line.
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5
上面是题目的简介。
程序思路:
f(n)是一个递推式,A、B为两个输入的参数,n表示迭代次数。以平常接数学题目时的思维来看,很简单,直接套公式,迭代n次肯定可以得到结果,下面是c语言实现代码:
#include "stdio.h"
#pragma warning(disable:4996)
int main()
{
int a, b;
long n;
long i;
int f[100];
f[0] = 1;
f[1] = 1;
while (scanf("%d %d %d", &a, &b, &n))
{
if (a < 1 || b > 1000 || n < 1 || n > 100000000)
return -1;
for (i = 2;i < n;i++)
{
f[i] = a * f[i - 1] + b * f[i - 2];
f[i] = f[i] % 7;
}
printf("%d\n", f[n-1]);
}
return 0;
}
然而,考虑到n的次数很大时,迭代次数也增加到相当大,其运算很明显会占用大量的时间。所以需要考虑响应的方法减小计算量,加快程序运行速度。
我们可以观察到公式所有的值都是经过mod7
运算的,通过对7取余,我们可以知道递推结果的数列中每个值的大小都是0~6
。每位有7种可能情况,递推公式中有两个数列的值输入,所以有7*7=49
种可能的组合。在所有的组合都出现之后,下一个情况必定是前面出现过的组合中的某一种,一次类推,重复出现,由此可以求到循环的周期。
利用循环周期,就可以很轻松地计算得到第n个对应哪一种情况了。
废话不多说,直接上代码吧。
#include "stdio.h"
#pragma warning(disable:4996)
int main()
{
int a, b, n;
int f[54] = { 0,1,1 };
int pos;
while (scanf("%d %d %d", &a, &b, &n) != EOF)
{
if (a < 1 || b > 1000 || n < 1 || n > 100000000)
return -1;
for (int i = 3;i < 54;i++)
{
f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
//printf("%d ", f[i]);
if (i > 5)
{
if (f[i - 1] == f[3] && f[i] == f[4])
{
pos = i - 4;
break;
}
}
}
//printf("\n");
if (n > 2)
printf("%d\n", f[(n-3) % pos+3]);
else
printf("1\n");
}
return 0;
}
补充:
- 为计算方便,从数组下标为1的元素对应数列第一个数,舍弃下标为0的那个元素;
- 关于循环,网上很多程序都是检测到前后两个分别为1、1的情况时就认为开始下一轮循环了;然而这种方法是错误的,因为如果取特例a=7、b=7时,输出序列为:1、1、0、0、0。。。。后面全部是0,这样程序会持续运行下去,因为不可能再检测到1、1了;所以检测循环时从第3个和第4个开始,检测是否重复:
if (f[i - 1] == f[3] && f[i] == f[4])
{
pos = i - 4;
break;
}
运行结果:
最新文章
- Ajax&;Java
- Underscore.js 初探
- Linux之Ganglia源码安装
- CHECKPOINT
- 【 随笔 】 D3 难吗?
- Prefix.pch的作用和用法
- cocos2dx lua调用C++类.
- 关于ActionContext.getContext()的使用方法心得
- mybatis 详解(六)------通过mapper接口加载映射文件
- 【动态规划】记忆搜索(C++)
- BZOJ4653 尺取法 + 线段树
- content_type
- Linux命令(六) 查看文件 cat tac more less tail
- 分布式部署下的报表调用 API调用 权限问题以及性能方案
- poj----2155 Matrix(二维树状数组第二类)
- OpenCV识别技术
- Java学习--jsp内置对象
- 【OC底层】OC对象本质,如 isa, super-class
- MySQL数据库如何与EXCEL的XLS格式相互转换
- Vue 组件与复用