华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1485|回复: 1
打印 上一主题 下一主题

约瑟夫问题

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2019-1-1 12:00:43 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
约瑟夫问题和斐波那契数列一样也是数学界的经典问题,里面有很多的数学原理和算法实现。
基本的约瑟夫问题是:有8个人围成一圈,编号分别为1-8,那么第8个人后面是第1个人。从第1个人开始,依次报数,报到5的那个人就出圈,下面的人又从1开始报数,同样报到5就出圈,请问出圈的顺序。


回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 2019-1-1 12:04:21 | 只看该作者

最直观的做法是模拟大法:用整数数组a(10)表示a(1)-a(8)八个人,若此人还在圈内设a(i)=1;若是已经出去了,则a(i)=0,这是一般的通用表示方法。这样当a(i)=1时候,s=s+a(i)就相当于s+1,报了下一个数,当a(i)=0时候,s=s+a(i)就不变,相当于第i个人出去了没有报数。实际上人还在只是没有参与统计。
用s表示现在报道了几,那么s==5的时候这个人要出去,下一个人要从0开始报。
每人报数完了之后下一个人接着报,i=i+1,但是第8个人之后接着的是第1个,所以if (i>8) i=1;
用k表示出圈的人的个数,那么对于此题应该是k<=7就做,第8个人出去后就不玩了。所以主程序可以写 while(k<=7)
循环初值些i=s=k=0 ;这个要体会一下。
  1. #include<iostream>
  2. using namespace std;
  3. const int mm=10;
  4. int a[mm];
  5. int i,k,s; ///i表示人的编号 s表示人的报数 k表示出去了几个人

  6. int main()
  7. {
  8.     for (i=1; i<=8; i++) a[i]=1; ///起始都是1
  9.     i=k=s=0;
  10.     while (k<=7)
  11.     {
  12.         i++;if (i>8) i=1;  ///第8个人后面是第1个
  13.         s=s+a[i];
  14.         if (s==5) {k++;///出去了一个
  15.         a[i]=0; ///再不统计
  16.         cout<<i<<' ';
  17.         s=0;///下面又重新开始
  18.         }
  19.     }
  20.     return 0;
  21. }
复制代码

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:59 , Processed in 0.211571 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表