设为首页收藏本站|繁體中文

Project1

 找回密码
 注册会员
搜索
楼主: 沙漠点灰

[讨论] 几个有意思的问题_第二弹

[复制链接]

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
72
在线时间
673 小时
注册时间
2006-10-3
帖子
1795

开拓者

发表于 2011-4-8 23:46:01 | 显示全部楼层
本帖最后由 熊猫 于 2011-4-8 23:57 编辑

我熊猫又回来啦
同时我也带来了我的最新的Prime计算代码:
  1.     Public Function Check_Prime(ByVal Num As Integer) As Boolean
  2.         Try
  3.             If Num = 1 Or Num = 2 Then Return True : Exit Function
  4.             Dim DefinedPrime As Integer = 0
  5.             Dim StartNum As Integer = 2
  6.             Dim NumSqr As Integer = Math.Sqrt(Num)
  7.             If PrimeSet.Count <> 0 Then
  8.                 If PrimeSet.Item(UBound(PrimeSet.ToArray)) > NumSqr Then
  9.                     For S As Integer = PrimeSet.Count - 1 To 0 Step -1
  10.                         DDNum += 1 '迭代计数器+1
  11.                         If PrimeSet(S) < NumSqr Then
  12.                             DefinedPrime = S
  13.                         Else
  14.                             Exit For

  15.                             'StartNum = PrimeSet(S) + 1
  16.                         End If
  17.                     Next
  18.                     For S As Integer = 1 To DefinedPrime
  19.                         DDNum += 1 '迭代计数器+1
  20.                         If Num Mod PrimeSet(DefinedPrime - 1) = 0 Then
  21.                             Return False
  22.                             Exit Function
  23.                         End If
  24.                     Next
  25.                 End If
  26.             End If
  27.             For S As Long = StartNum To Math.Sqrt(Num)
  28.                 DDNum += 1 '迭代计数器+1
  29.                 If Num Mod S = 0 Then Return False : Exit Function
  30.             Next
  31.             Call Add_Prime(Num)
  32.             Return True
  33.         Catch ex As Exception
  34.             MessageBox.Show(ex.Message)

  35.         End Try

  36.     End Function
复制代码
比起上一个版本,反向了一个循环,计算1000以内的Prime,迭代次数仅有6367次!少了一倍多。

点评

回来了?可喜可贺!我的1万多次全部是建立在1行搞定的基础上,多行的话,pass的太多了.....  发表于 2011-4-9 10:34
( ส็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็ ω ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้【看猫君玩,我也搞一只】)
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-9 00:12:50 | 显示全部楼层
回复 熊猫 的帖子

熊猫可以试试 Eratosthenes 筛法,构建 1000 内质数表只需要 917 次迭代。Atkin 筛法更优呢。

  1. BOUND = 1000
  2. primes = [ false, true ] * ((BOUND + 1) >> 1)
  3. primes[2] = true

  4. i = 3
  5. count = 0
  6. while i * i <= BOUND
  7.     if primes[i] then
  8.         j = i * i
  9.         while j <= BOUND
  10.             primes[j] = false
  11.             j += i
  12.             
  13.             count += 1
  14.             
  15.         end

  16.     else count += 1

  17.     end
  18.     i += 2
  19. end

  20. p count # 917
复制代码

点评

用删去的 嗯  发表于 2011-4-9 11:20
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
72
在线时间
673 小时
注册时间
2006-10-3
帖子
1795

开拓者

发表于 2011-4-10 14:58:40 | 显示全部楼层
回复 苏小脉 的帖子
  1. BOUND = 1000
  2. primes = [ false, true ] * ((BOUND + 1) >> 1)
  3. primes[2] = true

  4. i = 3
  5. count = 0
  6. while i * i <= BOUND
  7.     if primes[i] then
  8.         j = i * i
  9.         while j <= BOUND
  10.             primes[j] = false
  11.             j += i
  12.             
  13.             count += 1
  14.             
  15.         end

  16.     else count += 1

  17.     end
  18.     i += 2
  19. end
  20. for s in 1..10
  21.   p s.to_s + "  " +primes[i].to_s
  22. end
  23. p count
复制代码
我怎么感觉这个筛选得不对呢?我提取了10个结果。。都是false啊。。
( ส็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็ ω ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้【看猫君玩,我也搞一只】)
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-10 15:04:34 | 显示全部楼层
熊猫 发表于 2011-4-10 14:58
回复 苏小脉 的帖子

我怎么感觉这个筛选得不对呢?我提取了10个结果。。都是false啊。。 ...

最后那里 primes 的下标写成 i 了。。。
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
72
在线时间
673 小时
注册时间
2006-10-3
帖子
1795

开拓者

发表于 2011-4-10 17:53:23 | 显示全部楼层
回复 苏小脉 的帖子
  1. #include <stdio.h>
  2. #include <math.h>
  3. int main()
  4. {
  5.   int number;
  6.   int i;
  7.   int square;
  8.   int n;
  9.   int time=0;
  10.   scanf("%d",&number);
  11.   int num[number];
  12.   for (i=0;i<number;i++)
  13.   {
  14.     num[i]=i+1;
  15.   }
  16.   square = (int)(pow(number,0.5));
  17.   i = 0;
  18.   while (i<number)
  19.   {
  20.     if (num[i] % 2 == 0)
  21.     {
  22.       num[i] = 0;
  23.     }
  24.     i++;
  25.   }
  26.   for (n=3;n<=square;n=n+2)
  27.   {
  28.     i = n;
  29.     n = pow(n,2);
  30.     while (n < number)
  31.     {
  32.       num[n-1]=0;
  33.       n=n+2*i;
  34.       time+=1;
  35.     }
  36.     if (n>=number)
  37.     {
  38.       time+=1;
  39.     }
  40.     n = i;
  41.     }
  42.     printf("prime number 2\n");
  43.   for (i=0;i<number;i++)
  44.   {
  45.     if ((num[i]==0)||(num[i]==1))
  46.     {
  47.     }
  48.     else
  49.     {
  50.       printf("prime number %d\n",num[i]);
  51.     }
  52.   }
  53.   printf("iterated %d times\n",time);




  54. return 0;
  55. }
复制代码
嗯…………最终发布-Ultimate代码
迭代578次。。。远小于16000、12000、6000、5000、900……
某普渡大学在校学生供稿。。
QQ:249834305


为什么会比900那个少?是因为n=n+2*i;取代了原来那个代码的j += i。
如果直接加的话,奇数+奇数=偶数,所以这样没有必要判断,加n的2倍,奇数+偶数=奇数。这就少了400次迭代。
( ส็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็็ ω ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้【看猫君玩,我也搞一只】)
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-10 18:05:46 | 显示全部楼层
大家好,我是楼上代码的作者。。。
微末之技 不足挂齿。
不足之处,望大家指教~

评分

参与人数 2星屑 +260 收起 理由
enghao_lim + 60 不足之处?囧。比起来你比我厉害多了…….
熊猫 + 200 代码Developer

查看全部评分

回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-11 02:12:34 | 显示全部楼层
熊猫 发表于 2011-4-10 17:53
回复 苏小脉 的帖子

嗯…………最终发布-Ultimate代码

有意思!奇数相加那个真没想到 XD
不过这个版本的内层 while 循环外面没加上是否是质数的判断——只有质数的倍数需要被筛掉。
另外内层 while 下面那个 time += 1 会产生重复的计数(在进入了 while 的场合下)。

和我之前那个互补之后,迭代减少到了 462。
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-11 03:00:06 | 显示全部楼层
回复 苏小脉 的帖子

需要的,因为每一次判断都得算作一次迭代,所以不管通不通过while,都要算一次。
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
947 小时
注册时间
2007-4-25
帖子
805
发表于 2011-4-11 04:13:49 | 显示全部楼层
evolniar 发表于 2011-4-11 03:00
回复 苏小脉 的帖子

需要的,因为每一次判断都得算作一次迭代,所以不管通不通过while,都要算一次。 ...

先生所谓“每一次判断”为何?
学生且将“不管通不通过while,都要算一次”理解为“通过 while 则一次以上,不通过则一次”之意,然二十五楼代码却是“通过 while 则两次以上,不通过则一次”。

学生以为理当如此:

  1. if (B) { while (B) { ... ++times; ... } } else { ... ++times; ... }
复制代码
su@rpg.blue:~> repeat 1 fortune
Matz is nice, so we are nice.
回复 支持 反对

使用道具 举报

TA还没有解放自身的潜力。

Lv1.梦旅人

梦石
0
星屑
50
在线时间
3 小时
注册时间
2011-4-10
帖子
8
发表于 2011-4-11 11:00:10 | 显示全部楼层
苏小脉 发表于 2011-4-11 04:13
先生所谓“每一次判断”为何?
学生且将“不管通不通过while,都要算一次”理解为“通过 while 则一次以 ...

你看错啦,我的代码是,通过算一次,不通过也算一次~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

站长信箱:fux2@moe9th.com|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2019-6-18 03:45

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表