最近看到一個創(chuàng)新工廠的面試題，很有意思，下面給出算法實現（Java代碼）。如果哪位有更好的算法，請跟貼。

?????? abcde五人打漁，打完睡覺，a先醒來，扔掉1條魚，把剩下的分成5分，拿一份走了；b再醒來，也扔掉1條，把剩下的分成5份，拿一份走了；然后cde都按上面的方法取魚。問他們一共打了多少條魚，寫程序和算法

共打了多少條魚的結果有很多。但求最少打的魚的結果是3121條魚（應該找這5個人問問，用什么工具打了這么多條魚）

?

大家可以先用計算器驗證一下3121是否正確。

?

a開始拿魚：? （3121 - 1） / 5? = 625???

同理，bcde分別獲得的魚數（不包括其扔掉的魚）b:499?? c:399?? d:319??e:255

這道題最簡單的方法就是枚舉。從最小值開始，先看看代碼（Java實現）。

public class Test

{

?? public static void main(String[] args)

?? {

??????//? 分別保存a至e獲取的魚數（為了方便，包括其扔掉的魚）

????? int[] everybody_fish = new int[5];

?????? //?臨時數組，保存當前魚數減1后除5的余數，只有都為0，才滿足條件

????? int[] temp = new int[5];

?? ????//? 從1掃描到10000

????? for (int x = 1; x <= 10000; x++)

????? {

?????????? //?當前已被取走多少魚（包括被扔的魚）

??????? int sum = 0;

??????? int i = 0;

?????????? //?計算abcde各獲取的魚數

??????? for (i = 0; i < everybody_fish.length; i++)

??????? {

?????????? temp[i] = (x - 1 - sum) % everybody_fish.length;

????????????? //? 只要有一個人不能平均分配剩余的魚，就不滿足條件

?????????? if (temp[i] != 0)

????????????? break;

?????????? everybody_fish[i] = (x - 1 - sum) / everybody_fish.length + 1;

?????????? sum += everybody_fish[i];

??????? }

?????????? //?for循環(huán)正黨結束，滿足條件，輸出相應的值。

??????? if (i == everybody_fish.length)

??????? {

?

?????????? System.out.print("共釣了" + x + "條魚???? ");

?????????? for (i = 0; i < everybody_fish.length; i++)

?????????? {

????????????? System.out.print((char) ('a' + i) + ":"

??????????????????? + (everybody_fish[i] - 1) + "?? ");

?????????? }

?????????? System.out.print("最后剩余" + (x - sum) + "條魚??????");

?????????? System.out.println("扔了" + everybody_fish.length + "條魚");

??????? }

?????? }

??? }

}

運行上面的代碼，會輸出如下三行信息

共釣了3121條魚????a:624?? b:499?? c:399??d:319?? e:255?? 最后剩余1020條魚?????? 扔了5條魚

共釣了6246條魚????a:1249?? b:999?? c:799??d:639?? e:511?? 最后剩余2044條魚?????? 扔了5條魚

共釣了9371條魚????a:1874?? b:1499?? c:1199??d:959?? e:767?? 最后剩余3068條魚?????? 扔了5條魚

?

在10000以內只有三個數滿足這個條件。上面的代碼是通用的，如將兩個數組的長度改為6，將10000改成50000，會輸出如下信息。

?

共釣了46651條魚????a:7775?? b:6479?? c:5399??d:4499?? e:3749?? f:3124??最后剩余15620條魚?????? 扔了6條魚

?

也就是說一共6個人。每個人也是先扔一條魚，然后再將剩余的魚6等分，取走一份。 在50000以內只有46651滿足這個條件。

在本題中只有如下的代碼是核心算法，其他的都是枚舉和輸出結果的代碼。

for (i = 0; i < everybody_fish.length; i++)

{

??? temp[i] = (x -1 - sum) % everybody_fish.length;

? //? 只要有一個人不能平均分配剩余的魚，就不滿足條件

??? if (temp[i] !=0)

??????? break;

???everybody_fish[i] = (x - 1 - sum) / everybody_fish.length + 1;

??? sum +=everybody_fish[i];

}

總結

以上是生活随笔為你收集整理的创新工厂面试题详解：共打了多少鱼的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。