主题:有个问题请高手指点
步步高升(Step by Step)
——华南师大附中袁豪 2001分区联赛模拟赛 提高组第二题
【问题描述】
春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位,看到一盆叫做“步步高升”的盆竹。“步步高升,步步高升……”学习就是要一步一步来,不能急,要打好基础。在稳固的基础上才谈得上步步高升!TENSHI若有所思。她看到这盆东西好意头,于是想买下。谁知一问价钱,“不贵不贵,才2XXRMB。”TENSHI差点没昏倒,囊中羞涩嘛。但是TENSHI还是很想买下来,于是她就在一旁观察。观察了一段时间,她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元,那么他第i+1次报的价格为Wi-A或Wi -B。到了最后,TENSHI以Z元成交,高高兴兴的回家去了。
【任 务】
求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。
【输入格式】
从文件STEP.INP读入数据。文件第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件:
10 ≤ W1 ≤106,1 ≤ Z ≤ 106 ,Z < W1
2 ≤ A 、B ≤ 10000,A≠B
【输出格式】
直接把所求得的方法总数输出到文件STEP.OUT的第一行。文件只有一行(包括换行符)。注意:结果不超过MAXLONGINT
【样例一】
STEP.INP STEP.OUT
256 885 9 3889832
【样例二】
STEP.INP STEP.OUT
100 1013 23 0
[思路]
f (小于0)=0
f (0)=1
f (n)=f (n-A)+f (n-B)
w1-z=wi
程序如下:
program Step_by_Step;
const
size=15000;
var
w,z,ans,a,b:longint;
h:array[0..size] of longint;
fname:string;
procedure init;
begin
readln(fname);
assign(input,fname);
reset(input);
readln(w,z);
readln(a,b);
close(input);
end;
procedure main;
var i:longint;
begin
fillchar(h,sizeof(h),0);
h[w mod size]:=1;
for i:=w-1 downto z do
h[i mod size]:=h[(i+a) mod size]+h[(i+b) mod size];
ans:=h[z mod size];
end;
begin
init;
main;
writeln(ans);
end.
这个思路如何理解?
——华南师大附中袁豪 2001分区联赛模拟赛 提高组第二题
【问题描述】
春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位,看到一盆叫做“步步高升”的盆竹。“步步高升,步步高升……”学习就是要一步一步来,不能急,要打好基础。在稳固的基础上才谈得上步步高升!TENSHI若有所思。她看到这盆东西好意头,于是想买下。谁知一问价钱,“不贵不贵,才2XXRMB。”TENSHI差点没昏倒,囊中羞涩嘛。但是TENSHI还是很想买下来,于是她就在一旁观察。观察了一段时间,她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元,那么他第i+1次报的价格为Wi-A或Wi -B。到了最后,TENSHI以Z元成交,高高兴兴的回家去了。
【任 务】
求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。
【输入格式】
从文件STEP.INP读入数据。文件第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件:
10 ≤ W1 ≤106,1 ≤ Z ≤ 106 ,Z < W1
2 ≤ A 、B ≤ 10000,A≠B
【输出格式】
直接把所求得的方法总数输出到文件STEP.OUT的第一行。文件只有一行(包括换行符)。注意:结果不超过MAXLONGINT
【样例一】
STEP.INP STEP.OUT
256 885 9 3889832
【样例二】
STEP.INP STEP.OUT
100 1013 23 0
[思路]
f (小于0)=0
f (0)=1
f (n)=f (n-A)+f (n-B)
w1-z=wi
程序如下:
program Step_by_Step;
const
size=15000;
var
w,z,ans,a,b:longint;
h:array[0..size] of longint;
fname:string;
procedure init;
begin
readln(fname);
assign(input,fname);
reset(input);
readln(w,z);
readln(a,b);
close(input);
end;
procedure main;
var i:longint;
begin
fillchar(h,sizeof(h),0);
h[w mod size]:=1;
for i:=w-1 downto z do
h[i mod size]:=h[(i+a) mod size]+h[(i+b) mod size];
ans:=h[z mod size];
end;
begin
init;
main;
writeln(ans);
end.
这个思路如何理解?