1樓:QDelta
這是比較明顯的(
首先有乙個性質就是10的冪模9一定與1同餘再將十進位制正整數寫成各數字與10的冪之積之和,就可以發現數與其各位數之和是模9同餘的
那不斷地操作下去直到得到一位正整數,這個數又與原數模9同餘,可不就是它在[1, 9]中同餘的數。
建議題主可以考慮下如果9換成11這題可以怎麼出(
2樓:好逸惡勞勿入斯門
markdown公式不太會用,下面是手推的完整證明。應該是乙個數x的樹根dr(x)=(x-1)%9+1,也等於各位數字之和用sum表示時,dr(x)=(sum-1)%9+1。兩個公式是等價的,詳見手寫證明。
3樓:
上面的答案都寫的很好,也是LeetCode上看到這個問題,還是小白,就結合著上面的答案,舉個形象的例子:
首先:12345 = 1 * 9999 + 2 * 999 + 3 * 99 + 4 * 9
+ 5 + (1+ 2+ 3 + 4 + 5)
只要證明:12345 % 9 = (1 + 2 + 3 + 4 +5 ) % 9 就能往下遞推了。
那麼,我們已知:
m % 9 = a; n % 9 = b 即 m = 9 * x +
a; n = 9 * y + b;可推出
(m + n) % 9 = a + b = m % 9 + n % 9;
[1 * 9999 + 2 * 999 + 3 * 99 + 4 * 9 + (1+
2+ 3 + 4 + 5)] % 9 = (1 * 9999) % 9 + (2 * 999) % 9 + (3 * 99) % 9 + (4 * 9) %
9 + (1+ 2+ 3 + 4 + 5) % 9 = 0 + 0 + 0 + 0 + (1 + 2 + 3 + 4 + 5) % 9 = (1 + 2 +
3 + 4 + 5) % 9。
證明完成:12345 % 9 = (1 + 2 + 3 + 4 + 5) % 9 ;
因為題中最後乙個數恰好是小於10,與取mod 9結束也一致,所以:
(12345) % 9 = (1 + 2 + 3 + 4 + 5) % 9 = 12
% 9 = (1 +2) % 9 = 3 % 9 = 3。
4樓:
share一下理解公式的過程,ps我也是從leetcode上的題過來的
首先是公式,引用自維基百科Digital root嗯一下子沒看懂,然後在網上搜到了樓上說的那篇好文章感覺豁然開朗
需要利用構造法證明,
令1+2+3+4+5 = y
則dr(12345) = dr(y) = dr(9n+y)也就是說dr(y) = dr(9n+y)
令9n+y=X,則
dr(X) = dr(X%9)
X%9為個位數,所以dr(X%9) = X%9所以dr(X) = X%9
也有特殊情況,如果X為9的倍數,那麼在dr(12345) = dr(y) = dr(9n+y)中,y為9的倍數,則由dr(y) = dr(9n+y)得到dr(X) = dr(X%9)是不成立的。所以最後的結果也不成立,所以n為9的倍數的時候是特殊情況。至於為什麼dr(9n)=9,可以利用上面類似的思路證明。
久違的構造法啊,想了我好久
5樓:
DTStor – Data Storage / 【leetcode解題報告】258-Add Digits
請參考下這個博文~
6樓:Jin BV
今天寫演算法碰到這個問題
這個文章說的很好。
看這個應該就懂了:
12,345 = 1 × (9,999 + 1) + 2 × (999 + 1) + 3 × (99 + 1) + 4 × (9 + 1) + 5.
12,345 = (1 × 9,999 + 2 × 999 + 3 × 99 + 4 × 9) + (1 + 2 + 3 + 4 + 5).
7樓:
題目中命題錯誤!
題目中命題錯誤!
題目中命題錯誤!
重要的事情說三遍。
乙個數的數根為.因為正整數對9取模的結果取值為,,而數根的取值為。
之所以強調,是因為曾經參加比賽按照題目中的命題寫的錯了一次。
8樓:
假設有乙個n位的10進製數,我們寫成,其中表示從低到高的每一位因為 那麼
也就是乙個數和它的各數字之和的模9相同。
不如我們把這個操作記為f即
也就是所以
也就是說每做一次這樣的操作,它對於9的模始終是不變的所以最終求出的數根和原數對9的模相同。
9樓:
啊廢話,數根就是不斷地求這個數的各位數之和,直到求到個位數為止。所以數根一定和該數模9同餘,但是數根又是大於零小於10的,所以數根模9的餘數就是它本身,也就是說該數模9之後餘數就是數根。
阿西吧!
是否有方法證明乙個數是整數?
0.999.1,只不過是因為在實數的十進位制表示下,整數1還有另乙個表達方式而已 這裡把0.999.看成是柯西列 0.9,0.99,0.999,的極限,這是實數的十進位制表示的一種嚴密的定義 或者定義成是某個級數的和 鄭文超 接LZ的問題,我在SICP上碰到過乙個問題,讓你求證斐波那契數列的通項公式...
如何求乙個數的劃分 p n 個數??
riteme 雖然這個問題在知乎上是兩三年前提出的,我還是想給乙個簡單並且不是很慢的方法。首先,Wikipedia 上提到了下面這個遞推式 不過 Wikipedia 貌似沒有給出由來,我寫了一篇文章解釋了為什麼上面這個式子是正確的 計算分拆數的一種方法 riteme.site 上面的式子可以直接遞推...
是否可證明任意乙個數都可以用某個其他的數通過某種運算方法獲得
予一人 你的問題太過籠統。從最一般的意義上來說,運算 operation 就是一種函式 function 它將輸入的數按照某種確定的對應法則轉換為另乙個數作為輸出。具體來說,給定數集 和 若在某種對應法則 之下,對於任給的 都有某個 與之對應,則成立函式 也可記作 如此,對於任意兩數 我們可以強行定...