程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 九度OJ 1491 清華大學2012機試 《求1和2的個數》

九度OJ 1491 清華大學2012機試 《求1和2的個數》

編輯:關於C++
給定正整數N,函數F(N)表示小於等於N的自然數中1和2的個數之和,例如:1,2,3,4,5,6,7,8,9,10序列中1和2的個數之和為3,因此F(10)=3。輸入N,求F(N)的值,1= 輸入:
輸入包含多組測試數據,每組僅輸入一個整數N。
輸出:
對於每組測試數據,輸出小於等於N的自然數中1和2的個數之和,且對20123取模。
樣例輸入:
10
11
樣例輸出:

3

5


看了一份別人的代碼,十分簡略,不明白怎麼做的,就發到了論壇裡,有人給講解了,講得很棒

比如輸入12345,那麼先算F(1),再由F(1)算出F(12),依次再算出F(123),F(1234),F(12345);
主要計算的就是rslt=(rslt-cnt)*10+num*2+cnt*(t+1)+min(t,2);這一句了。
rslt是結果;num是實際輸入的數;cnt是num這個數中1,2的數量;


首先認為已經算出了F(12)=rslt,需要算F(123)


1.顯然12變成了12X的形式,所以原來1-11中每一個數都可以加上一個個位(因為不知道個位是不是9,所以最後一個12不能乘10,以後單獨計算),而個位是從0-9,所以原來的每個數都有10中變化,而最後一個數12的1,2的數量為cnt,所以有(rslt-cnt)*10,;

(比如比12小的有1,2的數是:1,2,10,11,擴大十倍後,有10-19,20-29,100-109,110-119,每個數各對應十個數,他們原本的的1和2被加了十次,所以乘以10)

2.上一步中余有一個12沒有計算,顯然12X這個數的個位只能是0-3,所以有cnt*(t+1);

(t是X位的數,cnt是12的1,2個數,為2,t從0開始,所以是cnt*(t+1)個)
3.上面的計算中都沒有考慮對個位為1,2的計數,00-11中個位為1,2的顯然是每10個數中有2個,所以有num*2
4.12X個位的1,2個數,直接判斷就好了,min(t,2);




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved