僞代碼/ Java神祕算法

我有一個算法，我想知道它的功能。我相信你們中的一些人可以看看這個，並告訴我它做了什麼，但我已經看了半個小時，但我仍然不確定。當我嘗試玩它時，它會變得混亂。你有什麼技巧來打破這樣的算法？我如何分析這樣的東西並知道發生了什麼？僞代碼/ Java神祕算法

我的猜測是它將數字從最小到最大排序，但我不太確定。

1. mystery(a1 , a2 , . . . an : array of real numbers) 
    2. k = 1 
    3. bk = a1 
    4. for i = 2 to n 
     5. c = 0 
     6. for j = 1 to i − 1 
      7. c = aj + c 
     8. if (ai ≥ c) 
      9. k = k + 1 
      10. bk = ai 
    11. return b1 , b2 , . . . , bk

這裏有一個相當於我試圖用Java寫的，但我不知道如果我翻譯正確：

public int[] foo(int[] a) { 
     int k=1; 
     int nSize=10; 
     int[] b=new int[nSize]; 
     b[k]=a[1]; 
     for (int i=2;i<a.length;){ 
      int c=0; 
      for (int j=1;j<i-1;) 
       c=a[j]+c; 
      if (a[i]>=c){ 
       k=k+1; 
       b[k]=a[i];

來源

2010-10-28 Snowman

作業？...... – 2010-10-28 05:59:20

最簡單的方法是取一小部分樣本並在紙上作業。在你的情況下，我們以號碼a[] = {3,6,1,19,2}。現在，我們需要逐步執行的算法：

初始化：

i = 2 
b[1] = 3

後迭代1：

i = 3 
b[2] = 6

後迭代2：

i = 4 
b[2] = 6

後迭代3：

i = 5 
b[3] = 19

後迭代4：

i = 6 
b[3] = 19

結果b[] = {3,6,19}

你可能已經猜到它在做什麼。

來源

2010-10-28 06:20:55 rkg

你的代碼是非常接近的僞代碼，但這些都是少數錯誤：

你for循環缺少增量規則：i++，j++
Java數組s是基於0的，不是基於1的，所以你應該初始化k=0,a[0], i=1，e.t.c.

而且，這不是排序，更多的是過濾 - 你元素的一些，但在相同的順序。

來源

2010-10-28 06:08:54 Kobi

我該如何分析這樣的東西並知道發生了什麼？

這樣的基本技術是用鉛筆和紙手工執行。

更高級的技術是將代碼分解成部分，找出部件的作用，然後在心理上重新組裝它。（訣竅是挑選分解的邊界，這需要練習。）

一旦你變得更好，你將開始能夠「讀」僞代碼......雖然這個例子可能有點對於大多數編碼人員來說，這樣處理起來太麻煩了。

來源

2010-10-28 06:10:57

轉換爲java時，請注意數組索引，因爲此僞代碼似乎暗示了基於1的索引。

從靜態分析：

一個是輸入並且不改變
b是輸出
ķ似乎是一個指針至b的元件，這將僅在遞增在某些情況下（所以我們可以將k = k+1看作是「下一次我們寫給b時，我們將寫入下一個元素」）
第6-7行中的循環完成了什麼？那麼c的價值是什麼？
使用先前的答案然後，當第8行是真的？
由於第9-10行僅在第8行爲真時執行，所以對輸出中的元素有何說法？

然後你就可以開始合理性檢查你的答案：

將輸出的所有元素來設置？
試圖通過僞碼與像[1,2,3,4]輸入運行 - 你會期望的輸出是什麼？

來源

2010-10-28 06:16:02

Google從來沒有停止過驚奇，因爲29日我拿它呢？ ;）

一個Java翻譯是一個好主意，一旦投入運行，你就可以一步看穿它的算法不正是，如果您有任何問題形象化它。

幾個要點：在僞代碼中有陣列通過n索引1，Java的陣列通過length - 1索引0。您的循環需要修改以適應此。你也已經離開了增量關閉您的循環 - i++，j++。

製作b魔法不變的尺寸也不是一個好主意 - 看看僞代碼，我們可以看到它被寫入最多n - 1次，所以這將是一個很好的起點。您可以調整它以適應最後。

最終尖端，該算法的爲O（n 2 ）定時。這是很容易確定 - 外for循環運行N次，內for循環的n/2倍，爲的總運行時間（n *（N/2））。在N * N占主導地位，這是什麼大O關注的是，使之成爲一個爲O（n ）算法。

來源

2010-10-28 06:16:51 Mania

+1給你好先生 – Joshkunz 2010-10-28 06:20:17

哦，並確保你把你的作業放在Seibel地下室的適當的保管箱中。 – Synesso 2010-10-28 06:22:13

哈哈哈我無法逃脫這些天的事情.. – Snowman 2010-10-28 19:41:38

def funct(*a) 
    sum = 0 
    a.select {|el| (el >= sum).tap { sum += el }} 
end

Srsly？誰發明了這些作業問題？

順便說一句：因爲這是同時使用了scan和filter在同一時間，和filter依賴於scan，其語言具有必要的功能，以這樣的方式簡潔地表達這一點，序列是唯一遍歷過一次？

來源

2010-10-28 13:13:34

僞代碼/ Java神祕算法

回答

相關問題