需要用一個數學腦筋急轉彎幫助

可能重複：
Easy interview question got harder: given numbers 1..100, find the missing number(s)需要用一個數學腦筋急轉彎幫助

嗨，大家好，我不知道在哪裏問這一點，但因爲這是一個算法問題，這裏有雲。我遇到了一個數學問題，在過去的幾天似乎無法克服它。它是這樣的：

您將得到一個增加機器款項一組由正整數1到N，因爲它給了數量（N + 1數字，例如機器給出 3作爲第一個數字和輸出3. 然後給出6作爲第二個數字和輸出9.它給出11作爲第三個數字和輸出20.等等，直到它處理了N + 1個數字）。重複一個（並且只有一個）數字是。你如何確定哪一個號碼被重複？

這似乎是一個詭異的問題，如果只是答案的答案是'不可能'的問題，我會非常惱火 - 這裏的任何想法？

來源

2010-09-16 Ali

你可以在這裏問這個問題http://math.stackexchange.com/ – codingbadger 2010-09-16 06:56:46

這個問題在你的問題中沒有說清楚，但是我認爲你給出了總數，但不是N.（如果你給了N，這將是一個可笑的簡單問題。） – 2010-09-16 06:59:02

重複http：// stackoverflow。com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-number（它也討論了一個更一般的版本） – 2010-09-16 07:11:54

從總和中減去（1 + 2 + .. + N）= N *（N + 1）/ 2。

編輯：如果N不知道，找到最大的三角形數小於給定的總和和減去。

來源

2010-09-16 06:56:56 Henrik

似乎不起作用... N指的是數字的數量，而不是它自己的值。 – Ali 2010-09-16 07:01:46

不等待我不明白它讓我們假設數字被添加爲3，6，11，6 - 所以現在N是4.我怎麼能告訴給我輸入6，只有值的總和？ – Ali 2010-09-16 07:05:18

@Ali：從您的描述中：「一組N + 1個數字，由正整數1至N組成」。但6和11在1..4之外。 – Henrik 2010-09-16 07:07:29

如果您知道N和總和S，答案是d = S - N*(N+1)/2。這是因爲從1到N的所有數字之和是triangular number，並且從1到N的每個數字都會出現一次（除了重複的數字之外）。

如果你不知道N，你可以拿N = floor((sqrt(8*S+1)-1)/2。這可以從二次方程(n^2 + n)/2 = a推導出。

來源

2010-09-16 06:59:12 viaclectic

我試圖與下列號碼[3,6，10] = 19，加入6到這筆款項給我25，以4×（4 + 1） = 20,20/2 = 10但25 - 10給我15 ...我想告訴一個數字是否重複，哪一個是？這是數學的分支嗎？ – Ali 2010-09-16 07:09:43

這些不符合您的問題描述。這些數字不屬於1..3。不僅如此，4不是N，而是N + 1。至於分支，它是基本組合。 – viaclectic 2010-09-16 07:11:11

如果你在這個問題中取任意數字，除非你事先知道所有不同數字的總和，否則它基本上是不可解的。 – viaclectic 2010-09-16 07:12:02

好吧，你有：

X = 1 + 2 + ... + N + p, where 1<=p<=N

或者

X = N(N+1)/2 + p, 1<=p<=N

聲明：本

S(N) = N(N+1)/2

而且你知道，

S(N) < X < S(N+1), because 1<=p<=N

你可以找到N，通過找到S（N）使得S（N）X。

如果您已經找到S（N），從X中減去它並找到重複的數字。

來源

2010-09-16 07:14:32

需要用一個數學腦筋急轉彎幫助

回答

相關問題