淘寶實習(xí)招聘筆試題和面試題答案(二)

簡答題

　　第一題：7公斤米，50克砝碼，200克砝碼各一個，稱1350克米問最少要多少次，并編程回答。

　　我答，6次，可能一開始會想到 1350/250 + 2 = 7次，說明貪心無效。我不知道我的方法是不是很笨，用了遞推，或者你可以看成是動態(tài)規(guī)劃。轉(zhuǎn)化一下題目的意思就是1克和4克砝碼，問多少次稱出27克大米，F(xiàn)[N]代表N克大米最少需要多少次。

　　則有：

　　F[N]=min{F[N-1],F[N-4],F[N-5]}+1

　　代碼如下：

　　intfindmin(int weight)

　　{

　　int v= weight/50;

　　int f[150];

　　f[0]=0;f=1;f=2;f[3]=3;f[4]=1;

　　if (v<5) return f[v];

　　int i;

　　for (i=5;i<=v;i++)

　　f[i]=min(f[i-1]+1,f[i-4]+1,f[i-5]+1);

　　return f[v];

　　}

　　注：我一開始愣了很久，我在想，稱好的大米可以作為砝碼來用嗎??這樣就是另一種問題了吧。