poj-1012-约瑟夫问题

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30
题目大意:
有k个好人和k个坏人,从第一个人开始循环报数(即报到m后从1开始报),报到m的人被处死,要求全部的坏人都处死,好人留下,求出m。
这个代码就是有点慢,所以我打了个表


#include<iostream>
using namespace std;
int main()
{
    int k;
    while(cin>>k)
    {
        if(!k)
            break;

    int m=1;
    int ans[30]={0};
    for(int i=1;i<=k;i++)
    {
        ans[i]=(ans[i-1]+m-1)%(2*k-i+1);
        if(ans[i]<k)
        {
            i=0;m++;
        }
    }
    cout<<m<<endl;

    }

    return 0;
}

    }
    sort(yes,yes+n,cmp);

    sort(no,no+n,cmp);
    cout<<yes[n-1]<<" "<<no[n-1]<<endl;


    return 0;


}
#include<stdio.h>
int main()
{
	int k;
	int Joseph[14]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
	while(scanf("%d",&k),k)
		printf("%d\n",Joseph[k]);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏進无尽的文章

益思维-早期苹果员工胸牌背面写的11条“成功法则”

早期苹果员工胸牌背面写的11条“成功法则”这个胸牌的背面写着11条成功法则,其中每一条文字都充满了正能量。从中我们可以看到一些触动人心的感觉。

10120
来自专栏一个会写诗的程序员的博客

服务网格 Pattern: Service Mesh

自从几十年前首次引入以来,我们了解到分布式系统能够实现我们之前甚至无法思考的用例,但它们也会引入各种新问题。

14520
来自专栏進无尽的文章

什么才是优秀的网站用户界面设计

17420
来自专栏数据库新发现

思科CEO钱伯斯:我非常尊敬华为

--------------------------------------------------------------------------------...

32310
来自专栏ios 技术积累

UIProgressView 当前进度显示圆角

也就是把 UIProgressView的trackTintColor设置为透明。假如进度条没有填满是效果是这样的

83820
来自专栏李蔚蓬的专栏

自定义控件基础 之 3.4 ViewGroup的测量 & 3.5 ViewGroup的绘制

之前分析中说了,ViewGroup会去管理其子View,其中一个管理项目就是负责子View的显示大小。当ViewGroup的大小为wrap_content时,V...

11820
来自专栏数据库新发现

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉 中广网 10月04日 09:48

19330
来自专栏知道一点点

20种新颖的按钮风格和效果【附源码】

Codrops 给我们分享了一组新鲜的按钮样式和效果的集合。它们中的大部分效果都使用了 CSS3 过渡和伪元素,他们都有一个共同点,那就是都具有简单性,没有太多...

16910
来自专栏ios 技术积累

TableViewCell和百度地图手势冲突

如果要实现这个功能,出现的问题就是缩放地图不灵敏,上下拖动TableView就会跟着动 解决办法

31320
来自专栏AhDung

慎用Assembly.LoadFile()和Assembly.LoadFrom()

经测这俩方法会锁住文件,导致程序运行期间无法对load过的程序集文件进行更名/删除/覆盖等等操作,考虑用Assembly.Load()文件字节组替代:

41140

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励