| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1882 人关注过本帖
标题:真正难题来了,高手请进!!
只看楼主 加入收藏
lwamani
Rank: 1
等 级:新手上路
帖 子:16
专家分:0
注 册:2004-11-16
收藏
 问题点数:0 回复次数:26 
真正难题来了,高手请进!!
从1到100找出9个整数,使这9个数的倒数和等于1,有几组找出几组,没有也要用程序证明。请给出详细算法和程序。
昨天想了很长时间,没找到好的解决方案!
搜索更多相关主题的帖子: 难题 
2005-02-21 11:37
yuki
Rank: 2
等 级:新手上路
威 望:5
帖 子:508
专家分:0
注 册:2005-2-4
收藏
得分:0 

#include <stdio.h> #include <stdlib.h> #include <conio.h>

void print_array(int *box,int size); void collector(int *box,int pos,int size); int inverse_sum(int *box,int size);

void main() { int box[9]={0};

collector(box,0,9); getch(); }

int inverse_sum(int *box,int size) { int i; int sum=0; for(i=0;i<size;i++) { sum += 1.0/box[i]; } return sum; }

void print_array(int *box,int size) { int i; for(i=0;i<size;i++) { printf("%4d",box[i]); } printf("\n"); }

void collector(int *box,int pos,int size) { if(pos < size && pos >= 0) { int i,j;

for(i=1;i<=100;i++) { box[pos]=i; pos++; collector(box,pos,size); pos--; } } else { if(inverse_sum(box,size) == 1) { print_array(box,size); } } } 三个数字的时候我测试过可以通过,不过9个数字是不是有点太慢了。。。。。。。。。。。。。。(可能会花几天几夜)

[此贴子已经被作者于2005-2-21 17:06:42编辑过]


我们都在命运湖上荡舟划桨,波浪起伏使我们无法逃离孤行;如果我们迷失方向,波浪将指引我们穿过另一天曙光
2005-02-21 16:51
天使预备役
Rank: 2
等 级:论坛游民
威 望:3
帖 子:670
专家分:10
注 册:2004-4-6
收藏
得分:0 
没有也要用程序证明

什么意思????

差点把你忘了...
2005-02-21 16:57
Alfred
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2005-2-21
收藏
得分:0 

大体上可以用回溯的方法做。实际上就是把100个整数中选出9个整数的方案全部穷举一遍,逐个验证。(第一遍是1 2 3 4 5 6 7 8 9;第二遍是1 2 3 4 5 6 7 8 10;第。。。。。。)

可以用下面的方法去掉许多不必要的情况:9个数中最小的数一定小于9,所以选取第一个数的时候就可以把它限定在2~~9的范围内。现在不妨先选5。那么剩下的8个倒数的和就成了0.5,0.5/8=0.0625,1/0.0625约为16.13,也就是说,这8个数种必有一个小于或等于16,这样就可把第二小的数的选取范围定在6~~16。照这样下去,每一次选一个数之前都算一下范围,应该可以在短时间内出结果。

2005-02-21 20:51
lmr
Rank: 1
等 级:新手上路
帖 子:86
专家分:0
注 册:2004-12-9
收藏
得分:0 
本人比较粗,用了最笨的方法如下:
#include&lt;stdio.h&gt;
main()
{
int a,b,c,d,e,f,g,h,i;
 for(a=1;a&lt;101;a++)
 for(b=1;b&lt;101,b!=a;b++)
 for(c=1;c&lt;101,c!=a,c!=b;c++)
 for(d=1;d&lt;101;d++)
 for(e=1;e&lt;101;e++)
 for(f=1;f&lt;101;f++)
 for(g=1;g&lt;101;g++)
 for(h=1;h&lt;101;h++)
 for(i=1;i&lt;101;i++)
  if(1.0/a+1.0/b+1.0/c+1.0/d+1.0/e+1.0/f+1.0/g+1.0/g+1.0/h+1.0/i==1)
  printf("a=%d,b=%d,c=%d,d=%d,e=%d,f=%d,g=%d,h=%d,i=%d",a,b,c,d,e,f,g,h,i);
  getch();
  }
若真的要算出来,那真的要等了,如果你只算4个数,那只要0.001秒就行了。
2005-02-23 11:45
kaikai
Rank: 1
等 级:新手上路
帖 子:236
专家分:0
注 册:2005-1-7
收藏
得分:0 
还是Alfred 的方法好

Have you visit acm.tongji. lately?
2005-02-23 20:13
神vLinux飘飘
Rank: 13Rank: 13Rank: 13Rank: 13
来 自:浙江杭州
等 级:贵宾
威 望:91
帖 子:6140
专家分:217
注 册:2004-7-17
收藏
得分:0 
支持kaikai的看法

Alfred的方法的确很好。如果让我做,我也会那么做的。

淘宝杜琨
2005-02-23 20:35
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
TO: lmr 你的解题思路是对的,但是 if(1.0/a+1.0/b+1.0/c+1.0/d+1.0/e+1.0/f+1.0/g+1.0/g+1.0/h+1.0/i==1) 这句是不能得到正确的结果 1。浮点数是不能这样比大小的,有个精度问题 2.这是个埃及分数问题,要求是绝对相等,而浮点数计算(1.0/a+1.0/b+1.0/c+1.0/d+1.0/e+1.0/f+1.0/g+1.0/g+1.0/h+1.0/i)是有误差的。所以不调试就知道你的程序是不行的。

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-02-23 21:41
Knocker
Rank: 8Rank: 8
等 级:贵宾
威 望:47
帖 子:10454
专家分:603
注 册:2004-6-1
收藏
得分:0 
这个问题不是一个简单回溯就能解决的吧,感觉如果是从1~100中去找九个数入手,还有个大数计算的问题,比如:假定91,92,93,94,95,96,97,98,99的倒数之和为1,那么,浮点计算是行不通,上面我已经说明了,只有通分后相加,再比较分子分母,那么则有个大数计算的问题,速度不会太快。我有个感觉,应从分解1着手比较好,倒行逆施!

九洲方除百尺冰,映秀又遭蛮牛耕。汽笛嘶鸣国旗半,哀伤尽处是重生。     -老K
治国就是治吏。礼义廉耻,国之四维。四维不张,国之不国。   -毛泽东
2005-02-23 21:50
kaikai
Rank: 1
等 级:新手上路
帖 子:236
专家分:0
注 册:2005-1-7
收藏
得分:0 
@knocker
貌似撤远了...

Have you visit acm.tongji. lately?
2005-02-23 21:52
快速回复:真正难题来了,高手请进!!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.045545 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved