Small knowledge, big challenge! This article is part of the “Programmer’s Essentials
This article also participated in the “Digitalstar Project” to win a creative gift package and creative incentive money
A monkey carries 100 bananas. He is 50 meters away from home. The monkey wanted to bring back bananas, but he could only carry 50 bananas at a time, and he had to eat one banana for every meter he walked. How w many bananas can the monkey finally bring home?
public class Mb {
public static void main(String... arg) {
recursiveMove(100.50.50.1);
move(100.50.50.1);
//recursiveMove(3000, 1000, 1000, 1);
}
/** * loop algorithm *@paramTotal Total number *@paramCapacity Maximum number of * at a time@paramShort distance *@paramEatNum Number of meals eaten per metre walked *@returnThe amount left at home **/
public static void move(int total, int capacity, intdistanceint eatNum) {
// Have moved to the location, i.e. moved a few meters
int location = 0;
// The number left at the starting point of each move
int currentStartNum = total;
// The number left at the end of each move
int currentEndNum = 0;
// All remaining bananas move one position
while (location < distance && currentStartNum > eatNum) {
System.out.println("Current location" + location + "The rest" + currentStartNum + "A banana.");
// Each basket of bananas moves one position
// There is no point in going back
while (currentStartNum > eatNum * 2) {
if (currentStartNum > capacity) {
moveOnePosition(location, location + 1, capacity, eatNum);
currentStartNum -= capacity;
currentEndNum += capacity - eatNum;
} else {
moveOnePosition(location, location + 1, currentStartNum, eatNum);
// Go straight ahead
currentEndNum += currentStartNum - eatNum;
currentStartNum = 0;
}
// Do you need to move the rest
if (currentStartNum > eatNum * 2) {
moveOnePosition(location + 1, location, -1, eatNum);
currentEndNum -= eatNum;
}
}
currentStartNum = currentEndNum;
currentEndNum = 0;
location++;
}
if (location < distance) {
System.out.println("-- The monkey could not reach the end of the climb and starved to death --");
} else {
System.out.println("Make it to the finish line, the rest." + currentStartNum + "个"); }}/** * recursive algorithm *@paramTotal Total number *@paramCapacity Maximum number of * at a time@paramShort distance *@paramEatNum Number of meals eaten per metre walked *@returnThe amount left at home **/
public static void recursiveMove(Integer total, Integer capacity, Integer distance, Integer eatNum) {
// The location that has been moved to
Integer location = 0;
// The number left at the starting point of each move
Integer currentStartNum = total;
// The number left at the end of each move
Integer currentEndNum = 0;
stepMove(location, distance, capacity, currentStartNum, currentEndNum, eatNum);
}
private static void stepMove(int location, intdistanceint capacity, int currentStartNum, int currentEndNum, int eatNum) {
if (location < distance && currentStartNum > eatNum) {
// All remaining bananas move one position
System.out.println("Current location" + location + "The rest" + currentStartNum + "A banana.");
// Each basket of bananas moves one position
// There is no point in going back
currentEndNum = miniStep(location, distance, capacity, currentStartNum, currentEndNum, eatNum);
// Step forward
currentStartNum = currentEndNum;
currentEndNum = 0;
location++;
stepMove(location, distance, capacity, currentStartNum, currentEndNum, eatNum);
} else {
if (location < distance) {
System.out.println("-- The monkey could not reach the end of the climb and starved to death --");
} else {
System.out.println("Make it to the finish line, the rest." + currentStartNum + "个"); }}}private static int miniStep(int location, intdistanceint capacity, int currentStartNum, int currentEndNum, int eatNum) {
if (currentStartNum > eatNum * 2) {
if (currentStartNum > capacity) {
moveOnePosition(location, location + 1, capacity, eatNum);
currentStartNum -= capacity;
currentEndNum += capacity - eatNum;
} else {
moveOnePosition(location, location + 1, currentStartNum, eatNum);
// Go straight ahead
currentEndNum += currentStartNum - eatNum;
currentStartNum = 0;
}
// Do you need to move the rest
if (currentStartNum > eatNum * 2) {
moveOnePosition(location + 1, location, -1, eatNum);
currentEndNum -= eatNum;
}
return miniStep(location, distance, capacity, currentStartNum, currentEndNum, eatNum);
} else {
returncurrentEndNum; }}/ * * *@paramFrom start position *@paramTo Target position *@paramCount Number of moves *@paramEatNum The amount of food carried in a meter */
private static void moveOnePosition(int from, int to, int count, int eatNum) {
if(count ! = -1) {
System.out.println("From position" + from + "Move" + count + "To the place" + to + "Eat" + eatNum + "个");
} else {
System.out.println("From position" + from + "Return to position" + to + "Eat" + eatNum + "个"); }}}Copy the code