JAVA算法：猴子吃桃子（JAVA版本算法）

JAVA算法：猴子吃桃子（JAVA版本算法）

问题描述

猴子吃桃子 有一只猴子第一天摘了很多桃，觉得很高兴就立刻吃了桃总数的一半，然后觉得没吃饱又吃了3个。猴子感觉这样吃桃会立刻没有，于是就定下一个规矩： 

• 每次在奇数天吃剩余桃总数的一半再多加3个
• 每次在偶数天吃剩余桃的总数的一半再多吃一个。

请输入一个天数，使得该天数的剩余桃数正好为1，请输出猴子第一天共摘了多少个桃？

---

问题分析

我们采用“倒推法”，来寻找规律：

第1天：猴子摘了N个桃子；

第2天：剩余桃子数量为1，倒推第1天的情况。N/2 - 3 = 1 ，则 N = 8；

第3天：剩余桃子数量为1，倒推第2天的情况。N_2/2 - 1 = 1，则 N_2 = 4; 那么第1天的情况：N_1/2-3 = 4；则 N_1 = 14;

反过来想：

设输入的天数为n; 首先，找到问题入口： 
第1天时， 求剩余桃数：F(1) ; 其次，找到问题的递归方程，
在本题中，递归方程有两个:
若n天为奇数天：有F(n) = (F(n+1)+3)*2 
若n天为偶数天：有F(n) = (F(n+1)+1)*2 
其中，奇数天与偶数天相互递归。
最后，问题结束：当程序求到第n天时，F(n) = 1 已知。

---

算法设计

package com.bean.algorithmbasic;

import java.util.Scanner;

public class MonkeysEatPeaches {

	/*
	 * 问题描述：猴子吃桃子 有一只猴子第一天摘了很多桃，觉得很高兴就立刻吃了桃总数的一半，然后觉得没吃饱又吃了3个。
	 * 猴子感觉这样吃桃会立刻没有，于是就定下一个规矩： 
	 * 每次在奇数天吃剩余桃总数的一半再多加3个，每次在偶数天吃剩余桃的总数的一半再多吃一个。
	 * 请输入一个天数，使得该天数的剩余桃数正好为1，请打印出猴子第一天共摘了多少个桃？
	 * 
	 * 问题分解：设输入的天数为n; 首先，找到问题入口： 
	 * 第1天时， 求剩余桃数：F(1) ; 其次，找到问题的递归方程，
	 * 在本题中，递归方程有两个:
	 * 若n天为奇数天：有F(n) = (F(n+1)+3)*2 
	 * 若n天为偶数天：有F(n) = (F(n+1)+1)*2 
	 * 其中，奇数天与偶数天相互递归。
	 * 最后，问题结束：当程序求到第n天时，F(n) = 1 已知。
	 * 
	 */

	public static void main(String[] args) {
		System.out.println("请输入天数：");
		Scanner scanner = new Scanner(System.in);
		int day = scanner.nextInt(); // 输入值

		System.out.println(sumNum(day, 1));
	}

	private static int sumNum(int day, int count) {
		if (count % 2 == 0) {
			return sumEvenDay(day, count); // 偶数天数
		} else {
			return sumOddDay(day, count); // 奇数天数
		}
	}

	private static int sumOddDay(int day, int count) {
		if (count == day)
			return 1;
		else
			return 2 * (sumEvenDay(day, count + 1) + 3);
	}

	private static int sumEvenDay(int day, int count) {
		if (count == day)
			return 1;
		else
			return 2 * (sumOddDay(day, count + 1) + 1);
	}

}

程序运行：

请输入天数：
3
14