小數點之和

以下是一個編程面試練習題。
處理這個問題的智能方法是什麼？小數點之和

數字M以相反的順序存儲在數組中。例如，號碼274存儲以下數組中：

A[0]= 4 A[1]=7 A[2]=2

收件，鑑於數組A代表某些數的函數，返回的數目M * 17陣列的十進制表示的數字的總和大小可能非常大（超過2,000,000個元素）。

來源

2011-03-22 all_by_grace

您好我無法理解這個問題u能PLZ闡述它。你的意思是說你想把每個數字乘以4,7和217乘以4 * 17,7 * 17和2 * 17，然後取所有這些乘法的總和？ – 2011-12-13 07:05:42

任何人都可以解釋這個問題很明顯，我無法理解這個問題？ – 2011-12-21 12:45:45

以下代碼將在O（n）中執行此操作。

#include <iostream> 
#include <vector> 

int times_17_dec_digits_sum(const vector<int> &A) 
{ 
    int sum = 0, carry = 0; 

    for (int i = 0; i < A.size(); i++) { 
     int perdigitsum = A[i]*17+carry; 
     sum += perdigitsum % 10; 
     carry = perdigitsum/10; 
    } 

    return sum + carry; 
} 

int main() 
{ 
    std::vector<int> b; 
    b.push_back(3); 
    b.push_back(5); 
    b.push_back(1); 

    std::cout << times_17_dec_digits_sum(b) << std::endl; 

    return 0; 
}

來源

2011-03-22 22:12:59 brado86

你不需要兩次攜帶 - 一次攜帶就足夠了。例如：17 * 25 - 您將有7 * 25 = 175 => 17進位; 17 + 1 * 25 = 42，總結果爲425。當然，這與問題沒有直接關係，但說明進位不一定只有一位數字。 – brado86 2011-03-22 22:30:09

+1，我發佈了相同的解決方案，我怎麼能不同意:) – 2011-03-22 23:51:36

你可以通過預先計算的乘法數組（如[0,17,34 ...]）來優化它，並執行如下操作int predigitsum =預先計算的[A [1] – 2011-03-23 00:10:20

將數字分解（或者不要編寫）爲十進制數字。在容器上循環乘以17，取最後一位數字並將其與結果相加，將餘下的數字作爲餘數，並將其添加到下一次迭代中乘法的結果中。數組完成後，將餘數中的數字添加到結果中。

int times17(const std::vector<int>& a) { 
    int result = 0, remainder = 0; 
    for (std::vector<int>::const_iterator it = a.begin(), end = a.end(); it != end; ++it) 
    { 
     int tmp = 17* *it + remainder; 
     remainder = tmp/10; 
     result += tmp - remainder*10; 
    } 
    while (remainder > 0) { 
     result += remainder % 10; 
     remainder /= 10; 
    } 
    return result; 
}

來源

2011-03-22 22:09:54

想象一下，你在153中乘以153乘以17。這將是這個樣子：

但你實際上並不需要保存完整的結果;你只需要隨時添加數字。因此，在第一步之後，您知道最後一位數字是1，並且您攜帶了5.然後在第二步之後，您知道第二位數字是0，並且您攜帶了9.然後在第三步之後，您知道第三位數字是6，並且您攜帶2.當數字用完時，您只需添加進位數字。（您不能攜帶超過16個，因此您只有兩種情況需要考慮。）

來源

2011-03-22 22:10:40 Neil

，因爲你乘後添加的所有數字17，就可以計算出數字的和whlie對每個元素的打算：

17*3 = 51 => 5+1 = 6 
17*5 = 85 => 8+5 = 13 
17*1 = 17 => 1+7 = 8 

6 + 13 + 8 = 27 => 2+7=9

來源

2011-03-22 22:14:20

招數三：

代替17 x，使用(10 + 8 -1)x;然後
而不是10 x，輪班名額;然後
而不是8 x，移位。

E.g：

17 * [3,5,1] = 
7 * [3,5,1,0] + [0,3,5,1] = 
[3,5,1,0]<<3 - [3,5,1,0] + [0,3,5,1]

這些都是可以執行的元素方面非常快的操作：

A[i] = A[i]<<3 - A[i] + A[i+1];

來源

2011-03-22 22:36:58 Eelvex

回答

相關問題