Project1

标题: 几个有意思的问题_第二弹 [打印本页]

作者: 沙漠点灰 时间: 2011-4-3 09:39
标题: 几个有意思的问题_第二弹
呵呵，我胡汉三又回来了....这次又有几个问题!

经过上次事件后，我写的代码变得诡异起来了....
这次的难度较上次，较难，好吧，这次是三级考试...

1.大家都知道，按下F12是重置游戏，有没有办法让它不"重置"，而直接退出呢...?

2.请尝试重新定义Array类的max方法

3.我们经常会这样:
  actor = $game_actors[n]
  actor.hp -= damage
  其中:
  p $game_actors[n] == actor => true

  但是，数类对象就不行了:
  a = 5
  b = a
  b -= 1
  p b == a  => false
  (因为是共不共内存地址的问题...)现想在让两个个数类变量(类型不限)的值一直一样

4.defined?(Foo)和defined?(Foo())分别代表什么...?

5.现让一个雪碧对象(Sprite)向27度方向一直移动5像素点...但是实际上不会这样做,
  这是因为5太小了，加上雪碧(好吧，我承认我没有打广告)对象不支持浮点坐标,误差很大,请设计个方案，让误差尽量小....

6.来个简单了(终于....)如图...怎么回事...?

7.现在有一个数组array中有一堆(?)位图(Bitmap),现在请释放掉其中面积最大的一个

8.这是我们的一道数学题(我悲剧地错了,本来数学就不太好...):

0,1,2,3,4,5这6个数字组成的所有4位数中,要求：
  ①.没有重复数字
  ②.包含2，3，但是2,3不相邻
  问:有多少个

  在这要求用数组array包含所有符合要求的数字

9.最后一个，压轴题..!
  求1000以质数(貌似改叫素数了?)算法...!要求从下面2个要求任选一个
  ①.最(尽量)精简的代码
  ②.最(尽量)少的循环、迭代次数

什么?你要两个一起选...?不可能吧...?毕竟熊掌和鱼的兼容性不好....

答案照例，下次发布

作者: 蔚、蔚、 时间: 2011-4-3 09:48
提示: 作者被禁止或删除内容自动屏蔽

作者: 熊猫 时间: 2011-4-3 10:38
本帖最后由熊猫于 2011-4-3 10:41 编辑

1.F12的问题可以在DLL中封掉，PM我你的邮箱地址，到时候我发给你。
2.这个忘了，翻翻某个动物出版社介绍Ruby的书好像就有。
3.就像你举的例子，将变量a类化(也就是放到类中)就可以了。
4.不懂
5.5像素可不小啊，差不少呢只要是循环的话效果很明显。我在XNA中完全可以用Sprite实现右上27度移5像素

Update段
{
tex_x += (int)(5 * 0.89);
tex_y -= (int)(5 * 0.45);
}
Draw段
{
spriteBatch.Begin();
spriteBatch.Draw(Texture2D, new Vector2(tex_x, tex_y), Color.White);
spriteBatch.End();
}

复制代码

6.未定义的对象，在外部调用了私用对象造成的错误吧。
7.不熟悉
8.最傻瓜的方式是循环生成....然后输出结果，这个代码不难，就不写了。
9.我选择后者最高效的
Prime的算法，我认为最高效的是：
定义一个Prime的可伸缩数组(.NET中我用ArrayList)

Public Function Check_Prime(ByVal Num As Integer) As Boolean
Try
If Num = 1 Or Num = 2 Then Return True : Exit Function
Dim DefinedPrime As Integer = 0
Dim StartNum As Integer = 2
Dim NumSqr As Integer = Math.Sqrt(Num)
If PrimeSet.Count <> 0 Then
If PrimeSet.Item(UBound(PrimeSet.ToArray)) > NumSqr Then
For S As Integer = 0 To PrimeSet.Count - 1
If PrimeSet(S) > NumSqr Then
Exit For
Else
DefinedPrime += 1
'StartNum = PrimeSet(S) + 1
End If
Next
For S As Integer = 1 To DefinedPrime
If Num Mod PrimeSet(DefinedPrime - 1) = 0 Then
Return False
Exit Function
End If
Next
End If
End If
For S As Long = StartNum To Math.Sqrt(Num)
If Num Mod S = 0 Then Return False : Exit Function
Next
Call Add_Prime(Num)
Return True
Catch ex As Exception
MessageBox.Show(ex.Message)
End Try
End Function

复制代码

这是我写的质数计算代码，感觉是最高效且精简的。
核心判断就在于，如果一个数从1除到这个数的平方根都没有被整除的话这个数就是Prime。
还有一个数除以比这个数平方根小的所有Prime都没有被整除的话，这个数就是Prime。

作者: 沙漠点灰 时间: 2011-4-3 10:46
回复熊猫的帖子

1.麻烦不超过10字节的代码就可以搞定
2.这是叫你自己写，不是翻源代码
3.还可以更简单
4......
5.Sprite默认不支持浮点坐标...
6. 未定义 66 ? 66 是一个数
a = eval('66') => a = 66
7.....
8....
9.你要相信Ruby!太长了!

作者: fux2 时间: 2011-4-3 11:13
本帖最后由 fux2 于 2011-4-3 15:47 编辑

手机打字累，熊猫君这个素数算法不优秀哦

def getprime(max=3)
return "error" if max<3
prime=[]
for i in 3..max
fux=0
j=2
while j<sqr(i)&&fux==0
if i%j==0
fux=1
j+=1
end
end
prime<<i if fux==0
end
prime
end

复制代码

作者: 熊猫 时间: 2011-4-3 11:31
回复 fux2 的帖子

我感觉简单的话就势必要牺牲效率....
“一个数除以比这个数平方根小的所有Prime都没有被整除的话，这个数就是Prime”
按照这个可以大大减少迭代量。

另外，沙漠啊，第一个问题我只需要改DLL的一个字节就可以。比起10字节的代码哪个好？

作者: 沙漠点灰 时间: 2011-4-3 11:42
回复熊猫的帖子

1个字节...?
dll也有3个字节吧....?
牺牲效率。。。？我都说了鱼和熊掌的兼容性不好!
我考虑一下提前发答案...?

作者: 熊猫 时间: 2011-4-3 11:47
回复沙漠点灰的帖子

只需修改一个字节，我忘记那个16进制是要改成74还是75了。反正jnz改成jz或者什么的。
是啊，我注重的是效率不是精简啊。。

作者: 沙漠点灰 时间: 2011-4-3 11:51
回复熊猫的帖子

好吧!公布第1问的答案:
下面代码置顶:
$g ? exit: $g=0

作者: DeathKing 时间: 2011-4-3 12:44
本帖最后由 DeathKing 于 2011-4-3 12:45 编辑

1、从RGSS来说，Input模块应该可以检测到F12的敲击，就是不知道是Input的优先级高，还是重置的优先级高。当然，可以利用F12重置游戏时，对于某些特殊情况可以引起StackTooDeepError的特点，来捕获错误，并退出。

2、考虑到Array的可以容纳的对象可以是不同的，所以还是作弊为上策。
class Array
  def max
return self.sort.last
  end
end

3、a != b 是因为 a 和 b 的 hash 不一样，而 Fixnum 类的 == 是根据 hash 来判断的。下面的方法或许有点暴力，直接重定义 == 方法。
class Fixnum
  def ==(obj)
return self.class == obj.class
  end
end

4、Foo 被认为是常量标识符，defined?(Foo) 会检查是否定义了Foo常量，而 Foo() 即使是大写字母开头，也被认为是一个方法。

5、利用三角函数，这样，x坐标大概要移动4个像素。
move_x = (5 * cos(27 / ((2 * Math::PI))).to_i
moev_y = (5 * sin(27 / ((2 * Math::PI))).to_i

6、没猜测出来。

7、有点乱，有点麻烦。
class Array
  def dispose_bad_bitmap
max_area = 0
the_bad  = -1
self.each_index do |index|
   next unless self[index].is_a?(Bitmap)
   temp_area = self[index].width * self[index].height
   if temp_areo > max_area
      max_area = temp_areo
      the_bad  = index
   end
end
self[the_bad].dispose if the_bad != -1
  end
end

8、ary = [0,1,2,3,4,5]
ary = ary.permutation(4).to_a
ary.each do |e|
  if e[0] != 0
if e.include?(2) and e.include?(3)
   i = e.index(2)
   if e[i+1] != 3 and e[i-1] != 3
      puts e.to_s
   end
end
  end
end

输出：
[1, 2, 0, 3]
[1, 2, 4, 3]
[1, 2, 5, 3]
[1, 3, 0, 2]
[1, 3, 4, 2]
[1, 3, 5, 2]
[2, 0, 3, 1]
[2, 0, 3, 4]
[2, 0, 3, 5]
[2, 1, 3, 0]
[2, 1, 3, 4]
[2, 1, 3, 5]
[2, 4, 3, 0]
[2, 4, 3, 1]
[2, 4, 3, 5]
[2, 5, 3, 0]
[2, 5, 3, 1]
[2, 5, 3, 4]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 0, 2, 4]
[3, 0, 2, 5]
[3, 0, 4, 2]
[3, 0, 5, 2]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 1, 2, 4]
[3, 1, 2, 5]
[3, 1, 4, 2]
[3, 1, 5, 2]
[3, 4, 0, 2]
[3, 4, 1, 2]
[3, 4, 2, 0]
[3, 4, 2, 1]
[3, 4, 2, 5]
[3, 4, 5, 2]
[3, 5, 0, 2]
[3, 5, 1, 2]
[3, 5, 2, 0]
[3, 5, 2, 1]
[3, 5, 2, 4]
[3, 5, 4, 2]
[4, 2, 0, 3]
[4, 2, 1, 3]
[4, 2, 5, 3]
[4, 3, 0, 2]
[4, 3, 1, 2]
[4, 3, 5, 2]
[5, 2, 0, 3]
[5, 2, 1, 3]
[5, 2, 4, 3]
[5, 3, 0, 2]
[5, 3, 1, 2]
[5, 3, 4, 2]

8、MathN库里面已经有了……不写了。要走了……

作者: IamI 时间: 2011-4-3 13:01
F12
rescue Reset
exit
搞定。

作者: IamI 时间: 2011-4-3 13:03
本帖最后由 IamI 于 2011-4-3 13:04 编辑

6是Bom，去掉前三个字符即可

Orz连贴系统悲剧了？连贴我有错......

作者: 蕾米莉亚·斯卡雷特 时间: 2011-4-3 13:12
本帖最后由蕾米莉亚·斯卡雷特于 2011-4-3 13:13 编辑

求质数:

t = Time.new
number = 1000
array = []
number.times do |i|
array[i] = i % 2 == 0 ? false : true
end
pa = []
max = Math.sqrt(number)
3.step(max, 2) do |n|
if array[n]
(2 * n).step(number, n) do |i|
array[i] = false
end
end
end
array.each_index do |timers|
pa << timers if array[timers]
end
p pa
p Time.new - t

复制代码

咱的渣电脑运行起来这个渣算法, 1.14秒
= = 很长~~

作者: 沙漠点灰 时间: 2011-4-3 13:17
本帖最后由沙漠点灰于 2011-4-3 13:27 编辑

回复 DeathKing 的帖子

既然有人了，公布答案吧！
1.
$g ? exit: $g=0
2.
rray.send(:define_method,:max){self.sort[-1]}
3.
$abc = 0
alias $bcd $abc
$abc += 1
p $bcd == $abc => true

4.DK对了!(....)

5.因为不支持浮点坐标,不管怎么都有误差
减少误差方法:
一:精灵类追加2个浮点变量记录"真坐标",误差大大减小
二:用数组保存移动路径,每移动1帧调用shift

6.这是IO的编码不兼容(晕,不大可能兼容吧,Ruby是UTF-8)，不多说

7.
(array.inject{|a,i|a.width*a.height>i.width*i.height ? a:i}).dispose

8.伪代码如下:
("1000".."9999").inject([]){|a,i|a<<i if 判断}
判断有点长，就不写了(比如包含"2","3",不包括"23","32",与[6,7,8,9]无交集等等)，不过可以1行搞定

9.压轴..？还是可以1行搞定:

(3..1000).inject([2]){|a,i|a.all?{|b|i%b!=0}?a<<i:a}

共计迭代15620次

把步长设为2(偶数Pass掉), i大于根号b时直接返回true(为什么...?自己想)等方法可以把迭代次数降到12000次左右，

(3..1000).inject([2]){|a,i|a.all?{|b|i%b!=0}?a<<i:a}
呵呵，Ruby果然很强

p.s 主要是复习了一下Ruby参考手册(学的时候看不懂,现在终于懂了)，发现 inject太强了

作者: 蕾米莉亚·斯卡雷特 时间: 2011-4-3 14:17
求解 inject 的用法~~

作者: 沙漠点灰 时间: 2011-4-3 14:27
回复蕾米莉亚·斯卡雷特的帖子

格式范围.inject(默认值){|a,b|......}
若有默认值，把默认值赋给a,把范围的第一个值赋给b
......是指代码块,每迭代一次会有个返回值(Ruby的特殊之处,方法都有返回值),把这个
返回值赋给a,把范围的第二个值赋给b........一次类推，最后返回a

若没有默认值，把范围的第一个值赋给a,把范围的第二个值赋给b.执行代码块,返回值
赋给a.把范围的第三个值赋给b........一次类推，最后返回a

作者: IamI 时间: 2011-4-3 15:02
第一题另解XD，RM在按下F12时会在主轴上创建Reset类型并抛出，抓住并重置即可

rescue Errno::ENOENT
# 补充 Errno::ENOENT 以外错误
# 无法打开文件的情况下、显示信息后结束
filename = $!.message.sub("No such file or directory - ", "")
print("找不到文件 #{filename}。 ")
rescue Reset
exit
end

复制代码

第六题代码示例

s = File.open("1.txt").read
s[0,3] = "" if s[0] == 239
eval(s)

复制代码

BOM是UTF-8的标志，长度为3个字符，将之删去代码即可运行。

作者: 苏小脉 时间: 2011-4-3 19:25
1、
在所有脚本之前加一句：

$!&&exit

复制代码

这是图省事了，正途还是应该去捕获 `Reset' 异常。

2、

class Array
def max
inject(self[0]) { |max, elem| elem > max ? elem : max }
end
end

复制代码

3、
你举的两个例子性质不一样——前者的 `actor.hp -= damage' 是 `actor.hp = actor.hp -

damage' 的语法糖，其中有调用 `actor' 这个对象的 `hp=' 实例方法和 actor.hp 的 `-' 实

例方法的过程，但 `actor' 这个引用的值没有变。后者的 `b -= a' 是 `b = b - a'，直接改

变了 `b' 这个引用的值，而并不是调用了 `xxx=' 这样的 setter。和第二个例子中的运算对称

的应该是 `actor -= damage'，而这种调用方式同样会改变 `actor' 这个引用本身，除非 `-'

方法返回 self。不太清楚你是纯粹想模拟后者的指针反引用机制还是前者的成员变异机制。

4、
前者在当前 Binding 下名为 Foo 的常量已定义时返回 "constant"，否则返回 nil；后者在

当前 Binding 下名为 Foo 的方法已定义时返回 "method"，否则返回 nil。

5、
想继续用浮点运算的话可以通过 Float#round 四舍五入。熊猫那种是强制类型转换，在大部分语言中是直接抛弃小数部分的。

6、

eval "nil.send '66'"

复制代码

如果是 RMXP 的环境，顶层 self 默认已经是 nil。

7、

class Bitmap
def area
width * height
end
end
arr = [Bitmap.new(1,1), Bitmap.new(2,1), Bitmap.new(3,4),Bitmap.new(5,2)]
p arr
arr.max { |u, v| u.area <=> v.area }.dispose
# 位图释放分布
p arr.collect { |u| u.disposed? }

复制代码

8、
有泛用的排列算法，不过鉴于这里排列长度仅仅为 4，还是套四个循环简单：

arr = []
def get_next_possible_digits(*digits)
result, absence = [ ], [ true ] * 6
digits.each { |digit| absence[digit] = false }
free = 2 * ((absence[2] ? 0 : 1) + (absence[3] ? 0 : 1)) >= digits.size
[0, 1, 4, 5].each { |e| result << e if absence[e] } if free
result << 2 if absence[2] and digits[-1] != 3
result << 3 if absence[3] and digits[-1] != 2
result
end
for i in 1..5
for j in get_next_possible_digits(i)
for k in get_next_possible_digits(i, j)
for l in get_next_possible_digits(i, j, k)
arr << i * 1000 + j * 100 + k * 10 + l
end
end
end
end
p arr

复制代码

统计学方法：
2??3 => 共 P(4,2) 种排列
2?3? => 共 P(4,2) 种排列
?2?3 => 共 3^2 排列

互换 2 和 3 的位置排列方式翻倍，于是最后是 2*(2*P(4,2)+3^2)=66

9、
Golfer 的版本：

2.upto(1e3){|i|(2..i).one?{|j|i%j==0}&&p(i)}

复制代码

不过 one? 只有 Ruby 1.9 才有。在 RM 里的话只能：

2.upto(1e3){|i|(2...i).all?{|j|i%j!=0}&&p(i)}

复制代码

追求执行效率的参见这贴：
http://rpg.blue/forum.php?mod=viewthread&tid=140141
我（用主号）在33楼发过 Eratosthenes 筛法，而 Atkin 筛法是它的一个优化版，是目前公认最快的质数筛法。
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

作者: david50407 时间: 2011-4-3 21:31
1.
利用F12的特性...
"重载脚本"

exit if $runOnce
$runOnce = true

复制代码

作者: 沙漠点灰 时间: 2011-4-4 12:45
回复苏小脉的帖子

回3: 两个个数类变量(类型不限)的值
已经说明类型不限了.....
回9:
果然Golfer不追求效率
2.upto(1e3){|i|(2...i).all?{|j|i%j!=0}&&p(i)}
共计迭代78022次,比我
(3..1000).inject([2]){|a,i|a.all?{|b|i%b!=0}?a<<i:a}
的15620大多了

作者: 熊猫 时间: 2011-4-8 23:46
本帖最后由熊猫于 2011-4-8 23:57 编辑

我熊猫又回来啦
同时我也带来了我的最新的Prime计算代码：

Public Function Check_Prime(ByVal Num As Integer) As Boolean
Try
If Num = 1 Or Num = 2 Then Return True : Exit Function
Dim DefinedPrime As Integer = 0
Dim StartNum As Integer = 2
Dim NumSqr As Integer = Math.Sqrt(Num)
If PrimeSet.Count <> 0 Then
If PrimeSet.Item(UBound(PrimeSet.ToArray)) > NumSqr Then
For S As Integer = PrimeSet.Count - 1 To 0 Step -1
DDNum += 1 '迭代计数器+1
If PrimeSet(S) < NumSqr Then
DefinedPrime = S
Else
Exit For
'StartNum = PrimeSet(S) + 1
End If
Next
For S As Integer = 1 To DefinedPrime
DDNum += 1 '迭代计数器+1
If Num Mod PrimeSet(DefinedPrime - 1) = 0 Then
Return False
Exit Function
End If
Next
End If
End If
For S As Long = StartNum To Math.Sqrt(Num)
DDNum += 1 '迭代计数器+1
If Num Mod S = 0 Then Return False : Exit Function
Next
Call Add_Prime(Num)
Return True
Catch ex As Exception
MessageBox.Show(ex.Message)
End Try
End Function

复制代码

比起上一个版本，反向了一个循环，计算1000以内的Prime，迭代次数仅有6367次！少了一倍多。

作者: 苏小脉 时间: 2011-4-9 00:12
回复熊猫的帖子

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

BOUND = 1000
primes = [ false, true ] * ((BOUND + 1) >> 1)
primes[2] = true
i = 3
count = 0
while i * i <= BOUND
if primes[i] then
j = i * i
while j <= BOUND
primes[j] = false
j += i
count += 1
end
else count += 1
end
i += 2
end
p count # 917

复制代码

作者: 熊猫 时间: 2011-4-10 14:58
回复苏小脉的帖子

BOUND = 1000
primes = [ false, true ] * ((BOUND + 1) >> 1)
primes[2] = true
i = 3
count = 0
while i * i <= BOUND
if primes[i] then
j = i * i
while j <= BOUND
primes[j] = false
j += i
count += 1
end
else count += 1
end
i += 2
end
for s in 1..10
p s.to_s + " " +primes[i].to_s
end
p count

复制代码

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

作者: 苏小脉 时间: 2011-4-10 15:04

熊猫发表于 2011-4-10 14:58
回复苏小脉的帖子

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

最后那里 primes 的下标写成 i 了。。。

作者: 熊猫 时间: 2011-4-10 17:53
回复苏小脉的帖子

#include <stdio.h>
#include <math.h>
int main()
{
int number;
int i;
int square;
int n;
int time=0;
scanf("%d",&number);
int num[number];
for (i=0;i<number;i++)
{
num[i]=i+1;
}
square = (int)(pow(number,0.5));
i = 0;
while (i<number)
{
if (num[i] % 2 == 0)
{
num[i] = 0;
}
i++;
}
for (n=3;n<=square;n=n+2)
{
i = n;
n = pow(n,2);
while (n < number)
{
num[n-1]=0;
n=n+2*i;
time+=1;
}
if (n>=number)
{
time+=1;
}
n = i;
}
printf("prime number 2\n");
for (i=0;i<number;i++)
{
if ((num[i]==0)||(num[i]==1))
{
}
else
{
printf("prime number %d\n",num[i]);
}
}
printf("iterated %d times\n",time);
return 0;
}

复制代码

嗯…………最终发布-Ultimate代码
迭代578次。。。远小于16000、12000、6000、5000、900……
某普渡大学在校学生供稿。。
QQ：249834305

为什么会比900那个少？是因为n=n+2*i;取代了原来那个代码的j += i。
如果直接加的话，奇数+奇数=偶数，所以这样没有必要判断，加n的2倍，奇数+偶数=奇数。这就少了400次迭代。

作者: evolniar 时间: 2011-4-10 18:05
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-11 02:12

熊猫发表于 2011-4-10 17:53
回复苏小脉的帖子

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

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

和我之前那个互补之后，迭代减少到了 462。

作者: evolniar 时间: 2011-4-11 03:00
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-11 04:13

evolniar 发表于 2011-4-11 03:00
回复苏小脉的帖子

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

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

学生以为理当如此：

if (B) { while (B) { ... ++times; ... } } else { ... ++times; ... }

复制代码

作者: evolniar 时间: 2011-4-11 11:00
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-12 02:29

evolniar 发表于 2011-4-11 11:00
你看错啦，我的代码是，通过算一次，不通过也算一次~

while 结束后会立刻进入 if 内部 o_o

作者: evolniar 时间: 2011-4-12 04:40
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-12 07:22

evolniar 发表于 2011-4-12 04:40
while (n < number)

{

while 终止的时候，n >= number

作者: evolniar 时间: 2011-4-12 11:50
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-12 12:44

evolniar 发表于 2011-4-12 11:50
我明白你的意思了哈。
还有，我们的代码除了i与i*2，之外，没什么差别。
怎么会“互补”呢？怎么可能减少 ...

学生判断了外层循环变量 i 是否是质数，如果是则往后筛，否则不用筛，因为 i 的质因数的所有倍数在先前的迭代中已经都被筛掉了，其中就包含了 i 自己的所有倍数。

作者: evolniar 时间: 2011-4-12 14:46
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-12 15:20

evolniar 发表于 2011-4-12 14:46
你这个想法很好，我也考虑过了。
但是你有没有想过，每判断一次 i 是不是质数，也算一次迭代啊。。。所以 ...

学生前日见先生说“每一次判断都得算作一次迭代”时就颇为疑惑，不解先生对迭代的定义是什么。依 Wikipedia 定义，迭代是“通过从一个初始估计出发寻找一系列近似解来解决问题的过程”。在我们讨论的 Eratosthenes 筛法中，若是不计初始化，只剩枚举奇数和筛选这两个（循环）过程可被称为迭代。我们加入计数递增之处正是（处于相同循环之中的）一系列语句被循环执行了一次之时。

这里是否是质数的判断仅仅涉及到了一次数组的随机访问，O(1) 的时间并不会增加算法复杂度，反而会避免很多次不必要的循环。我们计算迭代次数纯粹是为了满足楼主在主楼的需求，但迭代次数只能针对算法时间复杂度，不能针对真实的执行效率。

作者: evolniar 时间: 2011-4-12 15:32
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-13 04:33

evolniar 发表于 2011-4-12 15:32
你的意思是，跳过i=9,15,21,27？
我对迭代(iteration?)的定义是：每进行一次一次判断，即为一次迭代
.

i 是所有合数的时候都跳过了。462 是我的答案，457 是不计没进入内层 while 的场合，但确实该计~

作者: evolniar 时间: 2011-4-13 06:14
提示: 作者被禁止或删除内容自动屏蔽

作者: 苏小脉 时间: 2011-4-13 06:22

evolniar 发表于 2011-4-13 06:14
while ((n==9)||(n==15)||(n==25)||(n==21)||(n==27))
你不认为这种方法太机械了么。
改成 if (((i!=3)&& ...

为什么要这么做？学生是根据筛选表判断的：

# 如果 i 是质数
if (primes[i])
// 筛选 i 的倍数
...

复制代码

作者: 心雪 时间: 2011-4-15 01:10
本帖最后由心雪于 2011-4-15 01:32 编辑

1、

$gks = Win32API.new("user32","GetKeyState","l","i")
$a = $gks.call(123)
class << Graphics
alias _heart_snow_update update
def update
if ($gks.call(123) != $a)
exit
end
_heart_snow_update
end
end

复制代码

2、

class Array
def max
max = self[0]
for i in self
if max < i
max = i
end
end
return i
end
end
p [1,3,5,6,7].max

复制代码

3、好吧我承认我没研究出来

4、

class SpriteEX < Sprite
def initialize
super
@sx = 0
@sy = 0
end
def x
return @sx
end
def y
return @sy
end
def x=(x)
@sx = x
super(@sx)
end
def y=(y)
@sy = y
super(@sy)
end
end
$abc = SpriteEX.new
$abc.bitmap = RPG::Cache.icon("001-Weapon01")
for i in 1..10
$abc.x = 0.5 + $abc.x
Graphics.update
end

复制代码

5、
nil.__send__("66")

6、理论神马的最讨厌了，明明p出来都是"method"
--------------------------
好吧我竟然忘了defined?也可以判断常量- -

7、

array_bitmaps = [RPG::Cache.icon("001-Weapon01"),RPG::Cache.icon("002-Weapon02"),RPG::Cache.icon("003-Weapon03")]
max = 0
maxi = 0
for i in 0...array_bitmaps.size
bitmap = array_bitmaps[i]
if bitmap.height * bitmap.width > max
max = bitmap.height * bitmap.width
maxi = i
end
end
array_bitmaps[maxi].dispose
array_bitmaps[maxi] = nil
GC.start

复制代码

8、没时间了……DFS+剔除23在一起的情况

9、（请勿在RM中测试）

require "mathn.rb"
pr = Prime.new
pr.each{|v| break if v > 1000;p v ;}

复制代码

至于说算法……

#include<stdio.h>
char a[1001]={0};
int kill_number(long n)
{
int i = 2;
while(i*n <= 1000)
{
a[i*n] = 1;i++;
}
}
main()
{
long i,result = 0;
for(i=2;i<=1000;i++)
if(a[i] == 0)
kill_number(i);
for(i=2;i<=1000;i++)
if(a[i] == 0)
result++;
printf("%ld\n",result);
system("pause");
}

复制代码

时间原因先用以前写好的C语言的玩意吧……有时间再改成Ruby

为什么要追求一行代码呢～难道您打算参加国际Ruby混乱代码大赛？

作者: 苏小脉 时间: 2011-4-15 05:11
回复心雪的帖子

4（实则是 5）、是 27°，不是 0° o_O

5（实则是 6）、这么写不会有 eval 的信息，得嵌两层 eval；

9、Prime.new 这个被废弃了，现代的程序应该使用单例 Prime.instance，其余所有实例方法都提供了相应的类方法，如：Prime.each { ... }。

至于算法……不妨看看之前的讨论 OvO
空间方面其实只需要 ceil(1001/8) 个字节呢。

为什么要追求一行代码呢～难道您打算参加国际Ruby混乱代码大赛？

先生有所不知，当年 Perl 界有一个很有名的竞赛叫做 Perl Golf Apocalypse，其目的就是使用最少的 stroke 来写出一段程序，此处 stroke 同时有“高尔夫球挥杆”与“键击”之意，乃是双关语。后来的 Code Golf 就是基于经典的 Perl Golf 模式而出现的竞赛，其网站是 Rails 搭建的，引入了 Python、PHP 和 Ruby。Golfing 自由其乐趣，同时也是帮助了竞赛者掌握语言的接口。

作者: 心雪 时间: 2011-4-15 06:49
手机没有回复功能……直接回这里吧……实则是5的问题他只说要增强精度而已嘛……那个角度只是引子不是么（强词夺理）实则是6，好吧我承认我没仔细看……
至于素数算法，用二进制的确可以优化空间复杂度，但是C没有bool类型，我又不熟悉位运算……
还有……先生这个称呼承担不起，咱只是个学生……而且请问您是如何判断咱的性别的呢=v=

作者: 匿名 时间: 2011-4-15 06:57

心雪发表于 2011-4-15 06:49
手机没有回复功能……直接回这里吧……实则是5的问题他只说要增强精度而已嘛……那个角度只是引子不是么（ ...

“先生”神马的只是为了符合上下文的样子（大雾）

作者: 苏小脉 时间: 2011-4-15 07:47
回复心雪的帖子

但是C没有bool类型，我又不熟悉位运算……

其实 bool 也需要一个字节，关键在于位的操作。最好是用单个元素尽量大的数组，比如 32/64 位 int，使得每次位运算都能充分利用当前 CPU 架构下的最大的寄存器，减少内存操作次数，嘿嘿。

还有……先生这个称呼承担不起，咱只是个学生……而且请问您是如何判断咱的性别的呢=v=

先生只是对有学问者的通称，含敬意，并无年龄性别之分，呵呵~

作者: fux2 时间: 2012-3-18 14:38
本帖最后由 fux2 于 2012-3-18 14:53 编辑

@evolniar @苏小脉
用evoniar的代码测试了一下，输入25结果输出也包含25，显然有bug，只要输入数为奇数并且可以开方，就会输出这个数，作者是否需要修正一下，我想不需要咱提供方法吧。

欢迎光临 Project1 (https://rpg.blue/)