首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >算法-经典趣题-渔夫捕鱼

算法-经典趣题-渔夫捕鱼

作者头像
joshua317
发布2021-09-08 15:36:01
发布2021-09-08 15:36:01
9000
举报
文章被收录于专栏:技术博文技术博文

一、问题

渔夫捕鱼问题是一个典型的递推问题,渔夫捕鱼问题的大意如下:

某天晚上,A、B、C、D、E 5个渔夫合伙捕鱼,捕到一定数量之后便停止捕鱼,各自到岸边休息。第二天早晨,渔夫A第一个醒来,他将鱼分作5份,把多余的一条扔回河中,拿其中自己的一份回家去了。渔夫B第二个醒来,也将鱼分作5份,扔掉多余的一条,拿走自己的一份。渔夫C第三个醒来,也将鱼分作5份,扔掉多余的一条,拿走自己的一份。渔夫D第四个醒来,也将鱼分作5份,扔掉多余的一条,拿走自己的一份。渔夫E第五个醒来,也将鱼分作5份,扔掉多余的一条,拿走自己的一份。问5个渔夫至少捕到多少条鱼呢?

二、问题分析

先来分析一下渔夫捕鱼问题。这里,每个渔夫醒来的时候,鱼的数量都应该是5的倍数再加1。为了保证所有的渔夫都可以按照上述方法来分鱼。

那么最后一个渔夫E醒来之后,鱼的数量至少应该为6。在他扔掉一条鱼之后,仍然可以平均分为5份。

那么渔夫D醒来的时候,鱼的数量应该为6×5+1=31;

渔夫C醒来的时候,鱼的数量应该为31×5+1=156;

渔夫B醒来的时候,鱼的数量应该为156×5+1=781;

渔夫A醒来的时候,鱼的数量应该为781×5+1=3906;

这是一个明显的递推的式子,递推公式如下:

Sn-1=5Sn+1

三、编程

代码语言:javascript
复制
package com.joshua317;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
	// write your code here
        int yufa, total;
        System.out.println("渔夫捕鱼问题");
        Fish fish = new Fish();
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入渔夫数量:");
        yufa = scanner.nextInt();
        total = fish.totalFish(yufa);

        System.out.printf("%d个渔夫至少合伙捕鱼数量为%d", yufa, total);

    }
}

class Fish {
    public int totalFish(int yufu) {
        int init;//定义一个初始变量
        int i;//循环的次数
        int total;//捕鱼的总数
        init = yufu + 1;
        i = yufu - 1;
        total = init;
        while (i != 0) {
            total = 5 * total + 1;
            i--;
        }

        return total;
    }
}

本文为joshua317原创文章,转载请注明:转载自joshua317博客 https://www.joshua317.com/article/76

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-09-03 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、问题
  • 二、问题分析
  • 三、编程
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档