| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1410 人关注过本帖, 1 人收藏
标题:猜一猜,做一做。
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:70 
呵呵,谢了。
这个问题很有意思,所以昨晚(应该是今天凌晨)睡前还有脑子里琢磨。于是形成了下面这段代码。
算法本质还是我上面分析的,只是不过利用一点数论知识进行了优化,并将输出与大数运算的过程融合在一起省去了中间计算的缓存部分,将空间复杂度降到了最低。
实际运算速度比我预想的好很多,我的电脑是联想Y470。这段代码的运行时间是4632毫秒。
程序代码:
#include<stdio.h>
int main()
{
    int a, b, c, i, j;
    for(c = i = 1; i < 10000; i++)
    if((c = c * 10 % 19) == 2)
    for(b = 2; b <= 9; printf("%d\n", b++))
    for(a = b * 10, j = 0; j < i; j++, a = a % 19 * 10)
    printf("%d", a / 19);
    return 0;
}

输出结果有21M之多,这里只摘了前面的一段给大家。有兴趣的可以编译执行一下我的代码,将输出重定向到文件看看所有的结果。
105263157894736842
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
105263157894736842105263157894736842
157894736842105263157894736842105263
210526315789473684210526315789473684
263157894736842105263157894736842105
315789473684210526315789473684210526
368421052631578947368421052631578947
421052631578947368421052631578947368
473684210526315789473684210526315789
105263157894736842105263157894736842105263157894736842
157894736842105263157894736842105263157894736842105263
210526315789473684210526315789473684210526315789473684
263157894736842105263157894736842105263157894736842105
315789473684210526315789473684210526315789473684210526
368421052631578947368421052631578947368421052631578947
421052631578947368421052631578947368421052631578947368
473684210526315789473684210526315789473684210526315789
105263157894736842105263157894736842105263157894736842105263157894736842
157894736842105263157894736842105263157894736842105263157894736842105263
210526315789473684210526315789473684210526315789473684210526315789473684
263157894736842105263157894736842105263157894736842105263157894736842105
315789473684210526315789473684210526315789473684210526315789473684210526
368421052631578947368421052631578947368421052631578947368421052631578947
421052631578947368421052631578947368421052631578947368421052631578947368
473684210526315789473684210526315789473684210526315789473684210526315789

重剑无锋,大巧不工
2012-02-29 08:19
墨清扬
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:294
专家分:817
注 册:2011-10-4
收藏
得分:0 
感谢二楼,不然想破脑袋都不行……我的想法是,就取三位来分析吧,……abc……,那么b=c×2%10。如果c的两倍大于10,多出来的1就加到a上,也就是a=b×2+c×2/10。当然c不是最后一位时b也要加上1或0。那么可以由此逆推。取一个数为最高位,记录下来并输出,接下来每一位都是上一位加上上上位模2的10倍,如果某一位和第一位相同就可以结束输出,那么几个变量就可以解决了。以题目为例,一开始是4,所以接下来是2 1,由于1为奇数,所以下一位是0,下下位是(10+0)/2=5。到8的时候,由于(6%2×10+8)/2=4,因此可以结束,当然4不能再输出。要输出很多位的话,可以用一个计数器,超过一定位数才可以结束。手机打字好痛苦……晚上再给程序吧……

酱油实习生
2012-02-29 08:22
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
杨大哥,真是不服不行啊。

梅尚程荀
马谭杨奚







                                                       
2012-02-29 08:28
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
以下是引用czz5242199在2012-2-28 21:32:34的发言:

经baidu得,将此数的最后一位放在最前面会是原数的两倍
讨厌的度娘

梅尚程荀
马谭杨奚







                                                       
2012-02-29 08:29
墨清扬
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:294
专家分:817
注 册:2011-10-4
收藏
得分:0 
忘了考虑一点,结束的那一位必须为偶数,比如2105就不行,虽然下一位产生2

酱油实习生
2012-02-29 08:34
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
以下是引用beyondyf在2012-2-29 08:19:05的发言:

呵呵,谢了。
这个问题很有意思,所以昨晚(应该是今天凌晨)睡前还有脑子里琢磨。于是形成了下面这段代码。
算法本质还是我上面分析的,只是不过利用一点数论知识进行了优化,并将输出与大数运算的过程融合在一起省去了中间计算的缓存部分,将空间复杂度降到了最低。
实际运算速度比我预想的好很多,我的电脑是联想Y470。这段代码的运行时间是4632毫秒。
#include
int main()
{
    int a, b, c, i, j;
    for(c = i = 1; i < 10000; i++)
    if((c = c * 10 % 19) == 2)
    for(b = 2; b <= 9; printf("%d\n", b++))
    for(a = b * 10, j = 0; j < i; j++, a = a % 19 * 10)
    printf("%d", a / 19);
    return 0;
}
输出结果有21M之多,这里只摘了前面的一段给大家。有兴趣的可以编译执行一下我的代码,将输出重定向到文件看看所有的结果。
105263157894736842
157894736842105263
210526315789473684
263157894736842105
315789473684210526
368421052631578947
421052631578947368
473684210526315789
105263157894736842105263157894736842
157894736842105263157894736842105263
210526315789473684210526315789473684
263157894736842105263157894736842105
315789473684210526315789473684210526
368421052631578947368421052631578947
421052631578947368421052631578947368
473684210526315789473684210526315789
105263157894736842105263157894736842105263157894736842
157894736842105263157894736842105263157894736842105263
210526315789473684210526315789473684210526315789473684
263157894736842105263157894736842105263157894736842105
315789473684210526315789473684210526315789473684210526
368421052631578947368421052631578947368421052631578947
421052631578947368421052631578947368421052631578947368
473684210526315789473684210526315789473684210526315789
105263157894736842105263157894736842105263157894736842105263157894736842
157894736842105263157894736842105263157894736842105263157894736842105263
210526315789473684210526315789473684210526315789473684210526315789473684
263157894736842105263157894736842105263157894736842105263157894736842105
315789473684210526315789473684210526315789473684210526315789473684210526
368421052631578947368421052631578947368421052631578947368421052631578947
421052631578947368421052631578947368421052631578947368421052631578947368
473684210526315789473684210526315789473684210526315789473684210526315789
杨大哥你把这么完美的代码贴出来了,让后来人情何以堪。里牛面面

梅尚程荀
马谭杨奚







                                                       
2012-02-29 08:38
laoyang103
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:内蒙古包头
等 级:贵宾
威 望:19
帖 子:3082
专家分:11056
注 册:2010-5-22
收藏
得分:0 
回复 11楼 beyondyf
  绝对的服

                                         
===========深入<----------------->浅出============
2012-02-29 08:40
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
呵呵,仔细看看结果会发现,前7个值是最小的原子值。之后的值都是它们的重复。
根据这个规律可以打表,想算多长算多长了。这样计算每一个值的时间复杂度是O(n),有时间得论证一下这个规律。

[ 本帖最后由 beyondyf 于 2012-2-29 08:46 编辑 ]

重剑无锋,大巧不工
2012-02-29 08:42
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
以下是引用墨清扬在2012-2-29 08:22:55的发言:

感谢二楼,不然想破脑袋都不行……我的想法是,就取三位来分析吧,……abc……,那么b=c×2%10。如果c的两倍大于10,多出来的1就加到a上,也就是a=b×2+c×2/10。当然c不是最后一位时b也要加上1或0。那么可以由此逆推。取一个数为最高位,记录下来并输出,接下来每一位都是上一位加上上上位模2的10倍,如果某一位和第一位相同就可以结束输出,那么几个变量就可以解决了。以题目为例,一开始是4,所以接下来是2 1,由于1为奇数,所以下一位是0,下下位是(10+0)/2=5。到8的时候,由于(6%2×10+8)/2=4,因此可以结束,当然4不能再输出。要输出很多位的话,可以用一个计数器,超过一定位数才可以结束。手机打字好痛苦……晚上再给程序吧……
期待你的代码。

梅尚程荀
马谭杨奚







                                                       
2012-02-29 08:44
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
以下是引用beyondyf在2012-2-29 08:42:44的发言:

呵呵,仔细看看结果会发现,前7个值是最小的原子值。之后的值都是它们的重复。
根据这个规律可以打表,想算多长算多长了。这样计算每一个值的时间复杂度是O(n),有时间得论证一下这个规律。
嗯,只要解决衔接问题吧。

[ 本帖最后由 有容就大 于 2012-2-29 08:52 编辑 ]

梅尚程荀
马谭杨奚







                                                       
2012-02-29 08:45
快速回复:猜一猜,做一做。
数据加载中...
 
   



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

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