C语言中用数组解约瑟夫问题

Python013

C语言中用数组解约瑟夫问题,第1张

#include<stdio.h>

#include<stdlib.h>

void main()

{

int y(int n,int m)

int p,q,r

printf("请输入参选人的个数p和开始的位置q：\n")

scanf("%d%d",&p,&q)

r=y(p,q)

printf("最后那个人的初始位置是：%d\n",r)

}

int y(int n,int m)

{

int i,j=0,s=0,l

int *a=(int *)malloc(sizeof(int))

int *b=(int *)malloc(sizeof(int))

for(i=0i<ni++)

{

a[i]=i+1

}

a[n]=-1

for(i=0j!=ni++)

{

if(a[i]==-1)

i=0

if(a[i]!=0 &&a[i]!=-1)

s++

if(s==m)

{

b[j]=a[i]

a[i]=0

j++

s=0

} 

}

for(i=0i<ni++)

{

printf("%5d",b[i])

}

printf("\n")

l=b[n-1]

return l

}

扩展资料：

大体思路如下：

①、read(a)

②、b:=1,c:=1{b为某一组的元素个数，c为累计所加到的数}

③、while c<a do (b:=b*2,c:=b+c){超过目标时停止加数}

⑥、c:=c-b{退到前一组}

⑦、x:=a-c{算出目标为所在组的第几个元素}

⑧、ans:=x*2-1{求出该元素}

⑨、write(ans)

参考资料：百度百科-约瑟夫问题

#include<stdio.h>

int main() {

int num[50],n,m,i,j

int len,start = 0,counter = 1

printf("总数 报数\n")

scanf("%d%d",&n,&m)

if(n < 0 || n > 50 ) n = 50

if(m < 1 || m > n) m = n/2

printf("人数:%d，报数:%d\n",n,m)

for(i = 0 i < n ++i) num[i] = i + 1 // 预填

len = n // len保留队列中现有人数

while(len) {

if(counter == m) {

printf("%d ",num[start])

for(j = start j < len - 1 ++j)

num[j] = num[j + 1]

--len

counter = 1

}

else {

++counter

++start

start %= len

}

}

printf("\n")

return 0

}

题目：有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出

　圈子，问最后留下的是原来第几号的那位。

1. 程序分析：这是一个比较经典的算法--约瑟夫环问题.

2.个人分析: 算法比较经典,对于这样的问题本应该使用链表的形式会比较容易.约瑟夫环算法

则体现了使用数组来完成链表该完成的功能,虽然形式上完全不相同,但却求出了

相同的结果.有异曲同工之妙.总之我个人认为是数组中非常经典的算法了.希望本

人写的代码不会叫大家啐骂!

3.程序源代码：

#include <stdio.h>

#define N 50

#define S 3

void main()

{

int a[N]

int i,k

int sum=N

k=0

for(i=0i<Ni++)

a[i]=i+1

for(i=0i<Ni++)

printf("%-4d",a[i])

printf("\n")

for(i=0i++)

{

if(sum==1)

break

if(a[i%N]!=0)

{

k++

}

if(k==S)

{

k=0

//printf("%4d",a[i%N])

a[i%N]=0

sum--

}

}

for(i=0i<Ni++)

if(a[i]!=0)

printf("\n最后一个数为:%d\n",a[i])

}

两年前念书的时候写的,献丑了!