随笔 - 47, 文章 - 10, 评论 - 8, 引用 - 0
数据加载中……

刚看到了一道小题,练习了一下

Lucy上了初中,她很喜欢数学,经常做数学奥林匹克的题目,可是今天她遇到了难题,于是就向她在南开大学上学的哥哥Feagle请教,聪明的哥哥不一会功夫就编程解决了妹妹的问题(^_^,南开大学的学生就是优秀)! 妹妹的题目是这样的:对给定的f(n) 当 n>=50025002 的时候,f(n)=n-5;当 n<50025002 的时候,f(n)=f(f(n+2005))。现在请您试试编程解决Lucy的难题!


输入
输入只有一个整数n,-2147483647<n<2147483647 。 
  输出
输出只有一个整数,f(n) 的值。
  样例输入 样例输出
50025002 50024997
  
  时间限制
  
对每个输入数据,程序应在5秒内给出结果。

我分别用递归和非递归做了一下,本来想把没个函数的运行时间算一下,我用的是clock(),结果是开始时间和结束时间是一样的,我也就没放上了,谁帮忙计算出这两个函数时间上的差异

 1 #include  < iostream >
 2 #include  < time.h >
 3 long  count_1( long  n);
 4 long  count_2( long  n);
 5 int  main( int  argc, char   * argv[])
 6 {
 7      long  n,result_1 = 0 ,result_2 = 0 ;
 8      while ( 1 )
 9      {
10     printf( " \nPlease Input A Number: " );
11     scanf( " %ld " , & n);
12     result_1 = count_1(n);
13     result_2 = count_2(n);
14     printf( " \ncount_1:%ld\ncount_2:%ld\n " ,result_1,result_2);
15     }

16 }

17
18 long  count_1( long  n)
19 {
20      long  i = 1 ;
21      while (i)
22      {
23          if (n >= 50025002 )
24          {
25             n -= 5 ;
26             i -- ;
27         }

28          else
29          {
30             n += 2005 ;
31             i ++ ;
32         }

33     }

34      return  n;
35 }

36
37 long  count_2( long  n)
38 {
39      long  m,tmp;
40      if (n >= 50025002 )
41         m = n - 5 ;
42      else
43      {
44         tmp = count_2(n + 2005 );
45         m = count_2(tmp);
46     }

47      return  m;
48 }

49

说一下那个非递归调用的算法吧。
把x做为+2005的次数,y作为-5的次数
如果n>=50025002,那么不需要做+的操作,所以
y-x=1
否则n<50025002,就需要先+2005,再-5,x和y同时+1
因此,最终y-x=1。
所以先将i设为1

说的有点乱,看一下就明白了。

posted on 2006-04-05 16:47 编程之道 阅读(311) 评论(2)  编辑 收藏 引用 所属分类: C/C++

评论

# re: 刚看到了一道小题,练习了一下  回复  更多评论   

嗨,谢了。

看来这里真是好地方呀。

我是新手,以后希望不吝赐教。

呵呵
2006-04-05 18:23 | 华剑缘

# re: 刚看到了一道小题,练习了一下  回复  更多评论   

找到了,用timeval结构可以,呵呵,count_1的效率大约是count_2的7倍。
Please Input A Number:1024

Start count_1:673480 count_1:50025019 End count_1:673780 Time used:300
Start count_2:673786 count_2:50025019 End count_2:675914 Time used:2128
2006-04-06 09:49 | 编程之道

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理