回合數

奶牛，如你所知，有沒有手指或拇指，因而無法發揮剪刀，紙，石頭「（也稱爲‘搖滾，剪子，布’，」滾裝，深水，Bo'和其他一些名字），以便做出任意的決定，比如誰先被擠奶。他們甚至無法拋硬幣，因爲使用蹄子很難折騰。

他們因此採用了「圓號」匹配。第一頭牛選出一個不到20億的整數。第二頭牛也是這樣。如果這些數字都是「整數」，那麼第一頭牛會贏，否則第二頭牛會贏。

如果N的二進制表示形式的N爲零或多於零，則稱該正整數N爲「整數」。例如，當以二進制形式寫入時，整數9是1001. 1001具有兩個零和兩個1;因此，9是一個整數。整數26是二進制的11010;因爲它有兩個零和三個，它不是一個整數。

顯然，它需要一段時間將數字轉換爲二進制數，所以贏家需要一段時間來確定。貝西想要作弊，並且認爲如果她知道給定範圍內有多少「整數」，她就可以做到這一點。

通過編寫一個程序，它會告訴許多圓形數字是如何出現在由輸入（1 < =啓動<完成< = 20億）給出的包容範圍內幫助她。

輸入（rndnum.in）第1行：兩個空格分隔的整數，分別爲開始和結束。

輸出（rndnum.out） 1行：一個整數，它是圓形的數字在包容範圍Start..Finish

採樣輸入

樣品的計數輸出

來源

2011-12-28 Danny Arsenic

爲什麼你不想轉換爲基地2？計算機將所有數字都以2爲基數存儲在內部，因此它不會減慢任何速度。 – 2011-12-28 05:50:57

我試過轉換基地2，它太慢了（請注意輸入範圍從1到2,000,000,000，請）。如果我必須計算所有這些整數並將其轉換爲基數2，則需要很長時間（超過10秒）。 – 2011-12-28 05:55:50

我強烈建議你花些時間學習離散數學。這是一個有約束的排列問題。 – 2011-12-28 06:27:41

我不認爲你瞭解你的任務。要求說明奶牛不能很容易地解決這個問題，但它並沒有說明你的程序不允許這樣做。

你的程序應該算出給定範圍內的「舍入」數字，如果不轉換成二進制，這很難做到。我認爲這就是你的任務實際上要求你做的事情。

如果你必須避免轉換爲二進制，還有另一種方法。可以設置大小爲16的陣列，包含下列值：

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4

其中表示1位中的數字零到15包容的數量。

然後，在給定數字上使用除法和模數，可以快速得到該數字（和0位）中的1位數。

在僞碼：

def getOneBits (num): 
    lookup[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; 
    oneBits = 0 
    for i = 1 to 8: 
     oneBits = oneBits + lookup[num % 16] 
     num = num/16 
    return oneBits 

xstart = 271828 
xend = 314159 
xcount = 0 
for i = start to end: 
    if getOneBits (i) <= 16: 
     xcount = count + 1 
print "There are " xcount " round numbers between " xstart " and " xend

順便說一句，使用的尺寸256（字節而不是半字節）的查找表用C編碼此，我可以得到時間縮短到約6秒，只需要一點點優化工作。

來源

2011-12-28 05:55:05 paxdiablo

感謝您的想法。我認爲它會起作用。 – 2011-12-28 06:01:39

需要針對Java的基本2代碼查詢的策略

回合數

回答

相關問題