回覆列表
  • 1 # 使用者4097518081775

    先放結論,8張。

    先考慮十位,10,20,20,50四張足以表達10,20,……,100十個數,而且無法再減少(窮舉法即可)。

    再考慮個位,1,2,2,5四張足夠表達1~10,且無法再減少。

    但(1,2,2,5,10,20,20,50)不是這個問題唯一的解,考慮到1+2+2+5=10,則可以將十位數鈔票中的20換成10(注意到把10去掉就不能得到30+),仍然可以得到1~100任意一個數,如果不換,我們也不需要個位數鈔票加和得10,最大隻需要9就可以了,所以可以把一張2換成1(把1去掉就不能得到3)。

    於是最少有8張,三個解,分別是:

    (1,1,2,5,10,20,20,50)

    (1,2,2,5,10,10,20,50)

    (1,2,2,5,10,20,20,50)

    而第三個解用同樣的鈔票數可以表達1~110任意數值,我認為是最優的。

    此外,可以看出想要表達1~K*100間的任意數只需要7+K張rmb即可。

    ————————-——割———————————

    以上是有2元的情況,但是畢竟現在2元不發行了也比較少見,不如考慮沒有2元的情形,這種情形要簡單一些,沒有多解,4元必須用4張1元表示,個位鈔票求和不能到10(不然就要再多一張),所以也不能把20換成10,所以最少需要9張,只有一個解:

    (1,1,1,1,5,10,20,20,50)。

  • 中秋節和大豐收的關聯?
  • 我家寶寶9個月,夜間總是要吃幾次牛奶,怎樣斷奶?