主题:转圈相除
yaoyinglong
[专家分:0] 发布于 2010-06-14 18:16:00
大家好!我在做作业是时碰见这样一个题:有人围成一圈(编号为1到17),从第1号开始进行1,2,3报数,凡报3者退出,写一个人又从1开始报数……直到最后只剩下一个人为止。请问此人原来的位置是多少号?把我编死了!我现在没辙了!请高手帮帮忙!感激不尽!
回复列表 (共11个回复)
沙发
elst5523183 [专家分:210] 发布于 2010-06-14 23:56:00
你试试这样..
定义一个整数数组.
0表示还在圈里.
1表示已退出
令设循环,内循环内定义一变量用来计算圈里的人数.当这人数是3的倍数,设该数组元素为1.
外循环,当圈里的人数等于1,结束.
板凳
雪光风剑 [专家分:27190] 发布于 2010-06-15 08:19:00
约瑟夫环问题,可以找数据结构的书来参考,一般是链表的经典入门例题
3 楼
yaoyinglong [专家分:0] 发布于 2010-06-15 12:33:00
那个数据结构我们下学期才学呢!
4 楼
yaoyinglong [专家分:0] 发布于 2010-06-15 12:34:00
哦!好的!我试试看!谢了哦![em8]
5 楼
alweeq86 [专家分:1170] 发布于 2010-06-19 17:43:00
[code=c]
#include <iostream>
int ChuQuan(int Num)//Num为总人数
{
int *arrayTemp=new int[Num+1];//定义一个标志位数组 1表示已出圈
for(int i=0; i<Num+1; ++i) arrayTemp[i]=0;//标志位清0 只用arrayTemp[1]~arrayTemp[Num]
int count=0;//计数,计出圈的个数
int indexNum=0;//记录最后出圈的下标
for(int j=1,k=0;;)
{
if(Num-count==2) break;//只剩下2个人无法再出圈
if(1==arrayTemp[j]){j++;continue;}//此人已出圈,继续
if(j>Num) j-=Num;
if(arrayTemp[j]==0) k++;
if(k==3) {arrayTemp[j]=1;indexNum=j;count++;k=0;std::cout<<"出圈:"<<j<<std::endl;}
j++;
}
std::cout<<"出圈结束"<<std::endl;
delete[]arrayTemp;
return indexNum;
}
int main()
{
int num=17;
std::cout<<ChuQuan(num);
}[/code]
随便写了个程序 仅供参考
6 楼
yaoyinglong [专家分:0] 发布于 2010-06-21 23:19:00
哦!很好!多谢啊!可是您能不能写个C语言版的吗?这个我看的不是很明白!感激不尽……
哦!我也写了一个!但是不能打印出来东西!我有检查不出来那出了问题?请您指教!谢谢……
#include <stdio.h>
#define N 18
main()
{
int i, t, n=N, m;
int a[N]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
L:
m=(n-1)-(n-1)/3;
for (i=1; i<n; i++)
{
if (i%3!=0)
for (t=1; t<=m; t++)
a[t]=a[i];
}
if ((n-1)%3==2)
{
a[1]=a[t-1];
a[2]=a[t];
for (i=3; i<=m; i++)
{
t=i;
a[i]=a[t-2];
}
}
else if ((n-1)%3==1)
{
a[1]=a[t];
for (i=2; i<=m; i++)
{
t=i;
a[i]=a[t-1];
}
}
else if ((n-1)%3==0)
{
for (i=1; i<=m; i++)
{
t=i;
a[i]=a[t];
}
}
n=m+1;
if (n!=1)
goto L;
printf("此人原来的位置为:%d",a[t]);
}[em8]
7 楼
雪光风剑 [专家分:27190] 发布于 2010-06-23 07:57:00
写点注释吧,看着都晕了。
而且为什么要goto呢?这明明是while循环嘛
8 楼
alweeq86 [专家分:1170] 发布于 2010-06-25 21:40:00
[code=c]
#include<stdio.h>
#include<malloc.h>
int ChuQuan(int Num)//Num为总人数
{
//int *arrayTemp=new int[Num+1];//定义一个标志位数组 1表示已出圈
int *arrayTemp=(int *)malloc((Num+1)*sizeof(int));
for(int i=0; i<Num+1; ++i) arrayTemp[i]=0;//标志位清0 只用arrayTemp[1]~arrayTemp[Num]
int count=0;//计数,计出圈的个数
int indexNum=0;//记录最后出圈的下标
for(int j=1,k=0;;)
{
if(Num-count==2) break;//只剩下2个人无法再出圈
if(1==arrayTemp[j]){j++;continue;}//此人已出圈,继续
if(j>Num) j-=Num;
if(arrayTemp[j]==0) k++;
if(k==3) {arrayTemp[j]=1;indexNum=j;count++;k=0; printf("出圈:%d\n",j); }//std::cout<<"出圈:"<<j<<std::endl;
j++;
}
//std::cout<<"出圈结束"<<std::endl;
printf("出圈结束");
//delete[]arrayTemp;
free (arrayTemp);
return indexNum;
}
int main()
{
int num=17;
//std::cout<<ChuQuan(num);
printf("%d",ChuQuan(num));
}[/code]
9 楼
alweeq86 [专家分:1170] 发布于 2010-06-26 16:50:00
我帮你改写成C语言版的了
10 楼
caomang [专家分:150] 发布于 2010-06-26 18:14:00
我发的第一个帖子就是约瑟夫环的问题
但是那个是C++的
C的百度下,很多。一般书上也有
我来回复