Re: [問題] 演算法

[march20 ()]

※ 引述《yaote (ted)》之銘言：
: 標題: [問題] 演算法
: 時間: Sat Jan 13 11:16:10 2007
:
:
:  以下是一所國外研究所的考試題目，是否能用程式跟圖解來解答這個問題?
:
:  I have a computer file containing 1,000,000 non-negative integers,
:  in no particular order.  Imagine that they are the membership numbers of
:  people who are enrolled in my internet club.  A new person wants to join
:  the club, and we need to find an unused number to allocate to them.  How
:  would you find, in a reasonable time, a number that was not already in the
:  file?
:
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc)
: ◆ From: 220.140.56.26
: 推 march20:全部加起來一定沒問題 XD                  71.136.235.216 01/13 11:58
: 推 march20:如果只需要一次的話.                      71.136.235.216 01/13 11:59
: 推 march20:不然長遠來看, 用些資料結構來放會比較賺   71.136.235.216 01/13 11:59
: 推 march20:喔, 為了避免 0 的問題, sum 完後再加1     71.136.235.216 01/13 12:07

馬上發現其實我想太麻煩了 (雖然那也是第一時間想到的)

只要找到 max 再加一就好.

max 根本就是一讀完檔就找到了

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 71.136.235.216
推 idicivik:這樣可能會有問題吧 如果max 是1000000 될
推 march20:原題沒給限制哩 (事實上給 float 也可啊XD
推 idicivik:題目有提到ㄟ nonegative integer
推 march20:請看上一篇 :P
推 Eventis:這是有問題的,既然都說是在電腦裡讀檔了.
→ Eventis:就會有overflow的問題.
→ Eventis:就算傳負值也會牽涉到data type....@@
推 march20:我覺得可以不用考慮 overflow, 因為都寫在
推 march20:檔案裡了, 就再進一位也是還好
推 march20:找 max 也只需要記目前最大值, 位數再多
推 march20:linked list  就搞定了.
推 march20:(沒說是什麼樣的 file, 就隨人解釋吧,
推 march20:我就當這些數字存成字串了 )