討論區快速選單
知識庫快速選單
傑米的攝影旅遊筆記 政府補助!學嵌入式+物聯網 程式設計俱樂部Facebook粉絲團
[ 回上頁 ] [ 討論區發言規則 ]
how to handle this case ?
更改我的閱讀文章字型大小
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/15 下午 07:53:01
There is a question as following.
Construct a file and it has 4,000,000 integers . Please input an algorithm that can generate those integers which aren't in the file . Assume that you own 100M memory space.
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/24 下午 07:42:51
要先指定整數的範圍有多大,否則無限解等於無解
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/24 下午 10:50:47
would you tell me what is your consideration ?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/25 上午 03:04:22
不曉得是否有精闢的解法,我想得到的最簡單的方法就是暴力法

1. 依最大的整數範圍準備相等數量的 bit 數,並將這些 bit 全設為 0 或 1
2. 把 4,000,000 筆的整數讀進來,將各個整數的對應的 bit 反轉
3. 檢查各 bit 哪個沒反轉的對應整數就是不在檔案中
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/26 上午 02:04:31


把那 4,000,000 筆的整數排序好,那麼那些沒在檔案中的整數就是:比最小值還小的那些、比最大值還大的那些、以及各值之間的那些。

若採用在磁碟做合併序法就不用去擔心 100M memory 的限制了
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/26 上午 09:32:21
can can handle this case under this constraint if those numbers can't be sorted ?
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/26 下午 12:30:40
既然是整數就可以排序,採用 Merge sort 可以不須在記憶體中處理,因題目沒指定整數範圍有多大,排序法是我想得到可處理的方法了,看其他大大還有沒有什麼高見
作者 : ray8508(dra)
[ 貼文 16 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 02:12:09
不好意思,請問使用排序會比暴力快嗎?
暴力解時間複雜度應該是θ(n),排序的話好像要θ(n log n)。
所以暴力解應該比較快吧。
(個人淺見,請不吝賜教)
作者 : ray8508(dra)
[ 貼文 16 | 人氣 0 | 評價 0 | 評價/貼文 0 | 送出評價 1 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 02:43:54
想錯了
不好意思
請忽視
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 04:41:14
因題目沒指定整數範圍有多大, 只能用排序法
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 04:48:53
其實題目改成 待檢測的整數資枓中,把那些不在那 4,000,000 筆的整數找出來

這樣會比較具體
作者 : ozzy123(ozzy) VC++優秀好手資訊類作業求救卓越專家C++卓越專家貼文超過4000則人氣指數超過30000點
[ 貼文 4498 | 人氣 37262 | 評價 11100 | 評價/貼文 2.47 | 送出評價 49 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 06:56:46
this question is a famous it firm in the world wide.
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 09:28:31

>this question is a famous it firm in the world wide.

喔...那他的標準答案是什麼
作者 : sunyear(coco) VC++卓越專家C++頂尖高手貼文超過2000則
[ 貼文 2421 | 人氣 1485 | 評價 6060 | 評價/貼文 2.5 | 送出評價 5 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/28 下午 11:24:57
>>this question is a famous it firm in the world wide.
>喔...那他的標準答案是什麼
這種題目沒什麼標準答案。
通常為了演示某種演算法而去設計題目(但不表示該演算法是標準答案)。
我知道的一個類似的題目:
給定一個最多包含40億個隨機排列的32位整數的順序檔案,找出一個不在檔案中的32位整數。
這是為了演示二分法(從二分法搜尋的變化)而設計的題目。
40億個並不是隨便給的,它略少於2的32次方,所以暗示一定有解。
樓主的題目,看起來就不是很嚴謹,例如整數是幾位元的整數都沒給,而這顯然和演算法有關係的。
四百萬筆整數,代表什麼?和可用100M記憶體有關嗎?沒有整數的位元數,又很難跟它連結。
100M的記憶體又包含什麼?100M資料區嗎?還是包括程式,OS...
不用暴力法,二分法通常是第二優先選擇。二分法是需要排序的,但當有人提出排序時,樓出又提出不能排序。
比賽中訂規則似乎是樓主一向的壞習慣 >"<
作者 : cxxlman(CxxlMan) C++優秀好手貼文超過1000則
[ 貼文 1036 | 人氣 3227 | 評價 1260 | 評價/貼文 1.22 | 送出評價 27 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2013/9/29 上午 03:05:52
腦筋急轉彎是吧

那把整數看成是指 c++ 的 int 好了,那麼最大範圍就是能填滿 int 的所有 bit 的最大值

取得 unsigned *data = new unsigned[(unsigned)-1)]; // 試過了太大 new 不出來, 所以只用來表達看法

 for(unsigned i = 0;i <= (unsigned)-1;++i)
    data[i] = i;

把 data 用洗牌法弄亂

把 data 前 4,000,000 筆寫入檔案, 之後剩下的就是沒在檔案中的整數資料了, 大功告成 , 這樣可以吧 :)

 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 13050 
2 青衫 4760 
3 simula 4690 
4 coco 4030 
5 白老鼠(Gary) 3670 
6 ozzy 2540 
7 Ben 2250 
8 Anderson 1960 
9 windblown 1650 
10 Kenny 1560 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2019 程式設計俱樂部 http://www.programmer-club.com.tw/
0.171875