我需要解決一個測試問題，該問題要求計算以X蘋果為起始量，Y每次吃蘋果，每次吃蘋果時添加蘋果時總共可以吃多少個蘋果1。我當(dāng)前的解決方案使用遞歸函數(shù)，因此如果Y小于X或給定X太大，則會導(dǎo)致無限循環(huán)。public class Apples{ // Counts iterations. If we eat less than we add new every, it'll loop infinetely! private static int _recursions; private static int _applesRemaining; private static int _applesEaten; public static int CountApples(int startingAmount, int newEvery) { if (newEvery > startingAmount) newEvery = startingAmount; Console.WriteLine("startingAmount: " + startingAmount + ", newEvery: " + newEvery); _applesRemaining = startingAmount; /* Eat 'newEvery' amount */ _applesRemaining -= newEvery; _applesEaten += newEvery; Console.WriteLine("Eat: " + newEvery + ", remaining: " + _applesRemaining); /* Get one additional candy */ _applesRemaining += 1; Console.WriteLine("Added 1."); if (_applesRemaining > 1 && _recursions++ < 1000) { CountApples(_applesRemaining, newEvery); } else { if (_recursions > 1000) Console.WriteLine("ABORTED!"); /* Eat the one we've just added last. */ _applesEaten += 1; } return _applesEaten; } public static void Main(string[] args) { Console.WriteLine(CountApples(10, 2) + "\n"); }}我怎樣才能使這更有效？可能有一種更優(yōu)雅的方法可以做到這一點，但我無法弄清楚。編輯：原始測試問題文本：/** * You are given startingAmount of Apples. Whenever you eat a certain number of * apples (newEvery), you get an additional apple. * * What is the maximum number of apples you can eat? * * For example, if startingAmount equals 3 and newEvery equals 2, you can eat 5 apples in total: * * Eat 2. Get 1. Remaining 2. * Eat 2. Get 1. Remaining 1. * Eat 1. */
3 回答
aluckdog
TA貢獻(xiàn)1847條經(jīng)驗 獲得超7個贊
這個問題的遞歸似乎有點矯枉過正，所以我建議另一種數(shù)學(xué)方法。
讓我們從我們總是至少吃 X 個蘋果的事實開始。真正的問題是在所有東西都吃完后總共會添加多少蘋果。
假設(shè) ni 將是 i “吃”后剩余的蘋果數(shù)量。然后：
n0 = X
n1 = X - Y + 1
n2 = X - 2Y + 2
...
ni = X - i(Y - 1)
求解 ni = 0 將得到 i - 吃掉所有東西所需的“進(jìn)食”次數(shù)：
ni = 0 = X - i(Y - 1) => i = X / (Y - 1)
現(xiàn)在我們知道要吃多少次了，所以要吃掉的蘋果總數(shù)是原來的 X 加上吃掉 Y 個蘋果的次數(shù)（因為每次這樣做時我們都會得到一個額外的蘋果）：
tot = X + roundDown(i) = X * roundDown(X / (Y - 1))
我們將結(jié)果四舍五入，因為設(shè)置 ni = 0 捕獲了部分“吃”，然后導(dǎo)致部分蘋果。
例子：
X = 7, Y = 3 => tot = 7 + roundDown(7 / (3 - 1)) = 7 + roundDown(3.5) = 10
starting with 7:
0 eaten, 7 remain
3 eaten, 1 gained, 5 remain
3 eaten, 1 gained, 3 remain
3 eaten, 1 gained, 1 remains
1 eaten, nothing gained, nothing remains
--
10 eaten in total
- 3 回答
- 0 關(guān)注
- 245 瀏覽
添加回答
舉報
0/150
提交
取消