[转帖]算法设计之迭代法(2)_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 3669 | 回复: 0   主题: [转帖]算法设计之迭代法(2)        下一篇 
mengyuanye
注册用户
等级:少校
经验:1413
发帖:108
精华:7
注册:2012-11-14
状态:离线
发送短消息息给mengyuanye 加好友    发送短消息息给mengyuanye 发消息
发表于: IP:您无权察看 2012-11-23 11:13:35 | [全部帖] [楼主帖] 楼主

参考答案:

1.#include<stdio.h>

#include<stdlib.h>
int main()
{
      int n;
      puts("input n: ");
      scanf("%d", &n);
      puts("过程:");
      printf("%d -> ", n);
      while (n != 1)
      {
            if (0 == (n&1))
            n = n / 2; //迭代关系式
            else
            n = n * 3 + 1; //迭代关系式
            printf("%d -> ", n);
      }
      printf("\b\b\b\b \n");//去掉多余的“ -> ” 
      system("pause");
      return 0;
}


2. 算法分析: 根据题意,阿米巴每3分钟分裂一次,那么从开始的时候将阿米巴放入容器里面,到45分钟后充满容器,需要分裂 45/3=15 次。而"容器最多可以装阿米巴2^20个",

即阿米巴分裂15次以后得到的个数是2^20 。题目要求我们计算分裂之前的阿米巴数,不妨使用倒推的方法,从第15次分裂之后的2^20个,倒推出第15次分裂之前(即第14次分裂之后)的个数,再进一步倒推出第13次分裂之后、第12次分裂之后、……第1次分裂之前的个数。设第1次分裂之前的个数为x0 、第1次分裂之后的个数为x1 、第2次分裂之后的个数为x2 、……

第15次分裂之后的个数为x(15),则有x(14)=x(15)/2,x(13)=x(14)/2,……x(n-1)=x(n)/2 (n >= 1) 因为第15次分裂之后的个数x(15)是已知的,如果定义迭代变量为x ,则可以将上面的倒推公式转换成如下的迭代公式: x=x/2 (x的初值为第15次分裂之后的个数2^20)让这个迭代公式重复执行15次,就可以倒推出第1次分裂之前的阿米巴个数。因为所需的迭代次数是个确定的值,我们可以使用一个固定次数的循环来实现对迭代过程的控制。

#include<stdio.h>
#include<math.h>
int main()
{
      int max = pow(2, 20);
      int n = 15;
      int i;
      int s = max;
      for (i=1; i<=n; i++)
      {
            s /= 2;
      }
      printf("开始的时候往容器内放了%d个阿米巴\n", s);
      getchar();
      return 0;
}


3. 算法分析:先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找,不好找,但如果思路一变,从第N到第1去,可得出下面的推导式:

第N只猴   第N只猴前桃子数目

6          s6=x, 即最后剩下的桃子数 

5          s5=s6*5/4+1
4          s4=s5*5/4+1
3          s3=s4*5/4+1
2          s2=s3*5/4+1


1          s1=s2*5/4+1, 即最初的桃子数 

s1即为所求。上面的规律中只要将s1-s5的下标去掉:

s=x
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1


很显然,这是一种迭代,所以可以用循环语句加以解决。

综观程序的整体结构,最外是一个循环,因为循环次数不定,可以使用While循环,其结束条件则是找到第一个符合条件的数。为了做出上面while循环的结束条件,还需进一步分析上述规律的特点,要符合题目中的要求,s2-s6五个数必须全部能被4整除,而s1不能被4整除,这个可作为条件。具体实现请参看源程序。

#include <stdio.h>
int main(void)
{
      int x, s;
      int i;
      for(x=0; ;x+=4)
      {
            s = x;
            for (i=0; i<5; i++)
            {
                  s = s * 5 / 4 + 1;
                  if (s % 4)
                  break;
            }
            if (i == 4)
            break;
      }
      printf("摘了%d个桃子, 剩下%d个桃子\n", s, x);
      getchar();
      return 0;
}
4. #include<stdio.h>
double F1(double x); //要求解的函数
double F2(double x); //要求解的函数的一阶导数函数  
double Newton(double x0, double e);//通用Newton迭代子程序
int main()
{
      double x0;
      double e = 10E-6;
      x0 = -6;
      printf("x = %f\n", Newton(x0, e));
      x0 = 6;
      printf("x = %f\n", Newton(x0, e));
      getchar();
      return 0;
}
double F1(double x) //要求解的函数   
{
      return x * x - 45;
}
double F2(double x) //要求解的函数的一阶导数函数   
{
      return 2 * x;
}
double Newton(double x0, double e)//通用Newton迭代子程序   
{
      double x1;
      do
      {
            x1 = x0;
            x0 = x1 - F1(x1) / F2(x1);
      } while (fabs(x0 - x1) > e);
      return (x0 + x1) * 0.5;
}




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论