在java中實現埃及算法

我想要使用加法，減法和比較來遞歸地找到Java中兩個數字的乘法。所以，我GOOGLE了，我發現Egyptian Algorithm符合問題的要求。在java中實現埃及算法

但是，我不知道如何在到達base case後找到乘法結果。

實施例：

13 x 30 

1 -- 30 

2 -- 60 

4 -- 120 

8 -- 240 //we stop here because the double of 8 is larger than 13

要找到的結果，我們從一個等於13其中它們1+4+8的left column和我們從right column添加其相對的號碼另一方面添加的數字它們所30+120+240 = 390這是結果。

但是現在如何以編程方式完成最後一部分？如何檢查要添加的數字？我希望你們明白我的觀點。僅需要提示。

來源

2012-11-01 Sobiaholic

你是否試圖自己做這個？你有任何代碼片段？ –

我實際上是在問問題的最後部分。不是如何編碼整個算法。我會在一分鐘內發佈我的代碼。 – Sobiaholic

好的 - 你有什麼問題的最後部分？ –

好吧，我用蠻力算法做了。不過這是一個BigO-（n）。我相信有更有效的方式來實現它。目前。我正在解決這個問題。

謝謝你們！

來源

2012-11-05 22:06:33 Sobiaholic

通過以相反的順序

每一次，如果您的multiplicant其餘（其開始等於你multiplicant）比在左側列中的數時，從減去左欄所創建的結果做一個循環您的乘數並將右列添加到結果中（從零開始）。

來源

2012-11-01 13:55:34 Jasper

我正在關注你的提示。 – Sobiaholic

您可能已經發現這維基百科article。

看看「分解」部分的最後部分。你會發現你必須實現的子算法。

來源

2012-11-01 13:55:46

我可以想到的實現分解的唯一方法是'for loops'。但我認爲這會非常緩慢並且成本太高。多個for循環和遞歸調用。而且我仍然不知道這將如何幫助我找到「權力」來找到最後的結果。明天我會繼續。 – Sobiaholic

下面是僞代碼來解決這個問題：

function egyptian(left, right) 
    prod := 0 
    while (left > 0) 
    if (left is odd) 
     prod := prod + right 
    left := halve(left) 
    right := double(right) 
    return prod

基本上，而不是等到最後，這樣更容易檢查模板的每一行，因爲它是創造，如果它屬於輸出總結。我在my blog討論這個算法。

來源

2012-11-01 14:32:23 user448810

你也可以給這個對分功能的僞代碼嗎？我很難弄清楚如何使用可用的操作完成這些操作。 – Jasper

此外，'奇怪'也是使用給定的操作有問題。 – Jasper

古埃及人用鵝卵石對。你也可以做到的。把一個數字減半，拿走一個，扔掉一個，拿走一個，扔掉一個，拿走一個，扔掉一個，等等，直到剩下一個;你保存的鵝卵石是原始數量的一半。查找一個數字是否奇怪是相似的：拿一個並反覆拋出一個，直到沒有一個或一個卵石留下，這告訴你該數字是偶數還是奇數。 – user448810

在java中實現埃及算法

回答

相關問題