黑马程序员技术交流社区

标题: 约瑟夫环交流 [打印本页]

作者: 魇影 时间: 2014-6-27 16:15
标题: 约瑟夫环交流

#include <stdio.h>
int main()
{
int p[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}; //代表15个
int a = 0; //a和b用来当作两个标记，用来指出哪个人应该退出去
int b = 0;
int i = 0; //i 用来计数退出去几个人，控制循环结束的
while (i!=14) //i 等于14之前一直循环，即退出去14个人的话循环结束
{
if (p[a]==0){<span style="line-height: 1.5;"> </span><span style="line-height: 1.5;">//如果a角标对应的位置为0（这个位置没有人），就不会有人报数，a和b继续往后</span>

复制代码

基础考试中遇到的问题：耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（C语言）
我还不会嵌套什么的，数学也不好，用最笨的方法做出来了，无聊拿出来晒一下。
自己动手，丰衣足食，没有百度，用的都是最最简单的语句，但感觉不错~:lol
另外大家可以当作无聊时练习，在这个基础思想上把它完善一下，比如如果20个人玩，数到4的人退出去。做到我们指定玩的人数，和数到几退出去，程序给出最后存活下来的人序号，欢迎交流看法和提出建议~

作者: 魇影 时间: 2014-6-27 16:17

/
#include <stdio.h>
int main()
{
int p[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0}; //代表15个人
int a = 0; //a和b用来当作两个标记，用来指出哪个人应该退出去
int b = 0;
int i = 0; //i 用来计数退出去几个人，控制循环结束的
while (i!=14) //i 等于14之前一直循环，即退出去14个人的话循环结束
{
if (p[a]==0){ //如果a角标对应的位置为0（这个位置没有人），就不会有人报数，a和b继续往后走
a++;
b++;
};
if (a>15) { //a走过角标15表示报数进行完一圈，把a变成0继续下一圈报数，b减少16为了保持a领先b的数字不变
a=0;
b=b-16;
};
if (!(p[a]==0)) //如果a角标对应的位置不为0（这个位置有人），这个人报一个数，再进行下面条件判断
{
if (a==b+2) { //这个人报数后判断，若a已经领先b两个人，说明此时报数的这个人报的是3（前两个人报的数字是1和2），
p[a]=0; //让这个人退出去（这个角标对应的元素变成0表示），并且让b来到a位置，继续报数计数
b=a;
i++; //记录退出去的人数，用来控制循环结束
}else
a++; //如果这个人报数后a还没有领先b两个人，说明这个人报的数字不是3，此时a加1为了领先b一个数，
//当a领先b两个数时表示有人报到数字3了，则执行上面的操作
};
}
for (int m=0; m<15; m++) {//最后数组中只剩下一个元素不为0
if (!(p[m]==0)) { //找到是哪个元素不为0，打印它，表示这个位置的人到最后都没有退出圈子
printf("%d\n",p[m]);
}
}
return 0;
}

复制代码

晕，代码不知道怎么回事没贴好

作者: TLTY 时间: 2014-6-27 17:22
我基础考试最后一题也是做的这个，我的代码是：

作者: TLTY 时间: 2014-6-27 17:24
#include<stdio.h>
#define N 15
int main(){
int a[N],n=N;
int i,j,z,w,c=0;
for(i=0;i<N;i++)
a[i]=1;
for(z=0;z<N;z++){
for(w=0;w<N;w++)
if(a[w]!=0)c++;
if(c%3==0||c==10){
for(i=0,j=0;i<N;i++,j++){
if(a[i]==0) {j--;continue;}
a[i]=j+1;
if(a[i]%3==0){
a[i]=0;
n--;}
}
}

else
{
for(i=0,j=c%3;i<N;i++,j++){
if(a[i]==0) {j--;continue;}
a[i]=j+1;
if(a[i]%3==0){
a[i]=0;
n--;}
}
}
if(n==1)break;
}
for(i=0;i<N;i++)
{
if(a[i]!=0)
printf("叛徒的原来序号是：%d\n",i);
}
return 0;
}

作者: 刘昭 时间: 2014-6-27 17:35
比较经典的问题，
楼主有没有背包问题的，分享一下~

作者: 完美世界 时间: 2014-6-27 17:44
我的基础题没有这个，也做了下~

#include <stdio.h>
struct Person
{
int s;//存储这个人报出得数
int count;//存储这个人得序号
int k;//用作标记，当k=1时，说明这个人离开了圈子，用不再报数
}per[15]={0};
int main()
{
int y=0;
for (int i=0; i<15; i++)//分配每个人得序号
{
      per[i].count=i+1;
}
for (int i=0,out=0; ; i++)//变量out存储离开圈子的人数
{
      if (i==15)
      {
         i=0;
      }
      if(per[i].k!=1)//没有被标记离开的人报数
      {
         y++;
         per[i].s=y;
         if (out==14)//当离开了14个人，剩下的最后一个人
         {
            printf("这个人得序号是%d\n",per[i].count);
            break;
         }
      }
      if (per[i].s%3==0&&(per[i].k!=1))//标记离开的人
      {
         per[i].k=1;
         out++;
      }
}
}

作者: TLTY 时间: 2014-6-27 18:16

刘昭发表于 2014-6-27 17:35
比较经典的问题，
楼主有没有背包问题的，分享一下~

我有：
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。
三、实验代码
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define Size 100
void LCSLength(int m,int n,char *x,char *y,int c[Size][Size],int b[Size][Size])
{ int i,j;
for(i=1;i<=m+1;i++) c[0]=0;
for(i=1;i<=n+1;i++) c[0]=0;
for(i=1;i<=m+1;i++)
for(j=1;j<=n+1;j++)
   { if(x==y[j])
   { c[j]=c[i-1][j-1]+1; b[j]=0; }
   else if(c[i-1][j]>=c[j-1])
   { c[j]=c[i-1][j];
      b[j]=1;  }
   else { c[j]=c[j-1];
         b[j]=2; }
   }
}
void LCS(int i,int j,char *x,int b[Size][Size])
{ if(i==0||j==0) return;
if(b[j]==0)
   {  LCS(i-1,j-1,x,b);
      printf("%c",x); }
else if(b[j]==1) LCS(i-1,j,x,b);
else LCS(i,j-1,x,b);
}
main()
{ int m,n,i;
int c[Size][Size],b[Size][Size];
char x[Size],y[Size];
printf("输入序列x的长度(小于100):");
scanf("%d",&m);
printf("输入序列y的长度(小于100):");
scanf("%d",&n);
i=1;
printf("输入 x的成员(不用空格,直接输入字符串):\n");
while(i<m+2)
      { scanf("%c",&x);
      if(x!='\0') i++;
      }
i=1;
printf("输入 y的成员(不用空格,直接输入字符串):\n");
while(i<n+2)
   {  scanf("%c",&y);
      if(y!='\0') i++;
      }
LCSLength(m,n,x,y,c,b);
printf("最长公共子序列:\n");
LCS(m+1,n+1,x,b);printf("\n");
}

作者: 完美世界 时间: 2014-6-27 18:39
这个问题的另一种简单的办法

int main()
{
int p[15]={0};
int i=0,k=0,h=0;
while (k!=-15)
{
      if (p[i]>=0)
      {
         h++;
         p[i]=h;
         printf("第%d个人报数%d\n",i+1,h);
      }
      if (p[i]%3==0&&p[i]>=0)
      {
         k--;
         p[i]=k;
         printf("第%d号的人离开，离开了%d个人\n",i+1,k);
      }
      i++;
      if (i==15)
      {
         i=0;
      }
}
printf("这个人是%d号\n",i);

}
作者: 邱蚓 时间: 2014-6-27 19:15
没遇到。。难道你们的基础题那么难吗
作者: fantacyleo 时间: 2014-6-27 20:26
算法设计上暂时没想到好的改进，只想到了在数据结构上做文章，没测试过，也不知道对不对：既然叫xxx环，干脆就构造一个头尾相连的环状链表，设置一个变量表示还剩几个人，然后就一直不停数下去，报到3的就删除相应节点，直到剩1个人。由于链表删除是常数时间，而从n人删到1人要的步数是对数级别（删除3的倍数，即每次删去1/3，剩余人数为原先的2/3），这样就可以把时间复杂度控制在对数级别，但代价是链表的空间开销是数组的2倍。
作者: fantacyleo 时间: 2014-6-27 20:35
更正：时间复杂度不是对数级别，而是log(n)*log(n)。用数组，每次都要走一遍长度为n的数组看某个人是否离开，时间复杂度是n*log(n)，用链表可以轻松删除已离开的人，减少每轮判定次数。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2