4.7假設(shè)零錢系統(tǒng)的幣值是{1，p,p^2,……，p^n},p>1,且每個錢幣的重量都等于1，設(shè)計一個最壞情況下時間復(fù)雜度最低的算法，使得對任何錢數(shù)y，該算法得到的零錢個數(shù)最少，說明算法的主要設(shè)計思想，證明它的正確性，并給出最壞情況下的時間復(fù)雜度。 4.8考察路線上有n個地點(diǎn)可以作為宿營地。一直宿營地到出發(fā)點(diǎn)的距離依次為x1,x2,……，xn,且滿足x1<x2<……<xn,每天他們只能前進(jìn)30千米，而任意兩個相鄰的宿營地之間的距離不超過30千米，在每個宿營地只住1天，他們希望找到一個行動計劃，使得總的宿營天數(shù)達(dá)到最少，求解這個問題。