[求助4]指针，给我点头绪 - 编程论坛

#2

wtyj1122007-07-31 08:47

用一个数组就搞定了啊我以前做过这个程序有点意思

#3

aipb20072007-07-31 09:31

循环数组，双向循环链表。

baidu google：约瑟夫环

#4

wtyj1122007-07-31 10:15

不用循环数组
只要一个数组用一个while语句两个if语句就搞定。
我的代码如下是20个学生数到3就出队列。
#include <stdio.h>

void main ()
{
int stu[20] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19};
int cout = 0;
int cout1 = 3;
int *p = &stu[2];
int pu;

while ( cout <= 20 )
{
if ( cout1 == 3 )
{
cout1 = 0;
pu = p-stu;
printf (" %d ", stu[pu]);
stu[pu] = -1;
}
p = &stu[( ( ( p - stu ) + 1 ) % 20 )];
if (*p != -1)
{
cout = 0;
cout1++;
}
else cout++;
}

}

#5

wtyj1122007-07-31 10:19

呵呵我说错了我这个就是循环数组。

#6

HJin2007-07-31 10:27

回复：（a8451727）[求助4]指针，给我点头绪

/*---------------------------------------------------------------------------
File name: C76-36.cpp
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/30/2007 19:12:41
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

经典 76 道编程题之 36:

36. 猴子选大王:
① N 只猴子站成一行，每隔 M 只从头到尾报数，反复进行,报过数的退出，打
印每次退出的猴子的编号,直到剩下一只为止。
② N 只猴子站成一行，每 M 只报数。先从头到尾，报到尾后，再返回从尾到头
报数，打印每次方向及过程，直到剩下二只时，以排到后面的(指报数方向)为大王。
③ N 只猴子围成一圈，从第 P 个开始，每隔 M 只报数，打印每次过程，只剩下
一个时为大王。

*/

#include <iostream>
using namespace std;

#define MAX 10000
int a[MAX+1];

int chooseKing(int n, bool simulate=false);

int main()
{
int n, king;

while(cin>>n)
{
if(n==0)
{
cout<<"Please input n (n > 0):\n";
continue;
}

king = chooseKing(n);

cout<<"The king is monkey #"<<king<<"."<<endl;
}

return 0;
}

int chooseKing(int n, bool simulate)
{
int i, s, left;

// a[i] = 1 means that the monkey is a candidate for the king
// = 0 means he is eliminated.
for(i=1; i<=n; ++i)
a[i] = 1;
s=0;
left = n;

// there is more than one monkey left
while(left>1)
{
if(simulate)
{
for(i=1; i<=n; ++i)
{
if(a[i])
cout<<i<<" ";
}
cout<<endl;
}
left=0;
for(i=1; i<=n; ++i)
{
s+=a[i];

if(s==3)
{
s=0;
a[i]=0;
}

left+=a[i];
}
}

for(i=1; i<=n; ++i)
if(a[i])
return i;

return -1; // will never reach here
}

#7

wtyj1122007-07-31 10:46

今天我见到传说中的约瑟夫环终极代码
见到这个代码我决定明天开始要努力恶补数学。数学真是好东西！！
#include <stdio.h>
#include <conio.h>
int main( void )
{
int n, i = 0, m, p;

scanf("%d%d", &n, &m); //n总人数，m步长
while( ++i <= n )
{
p = i * m;
while (p > n) p = p - n + (p - n - 1)/(m - 1);
printf("%d\n", p);
}
return 0;
}

#8

wtyj1122007-07-31 10:48

没有循环没有数组没有链表只有纯数学抽像
使问题最简单。。牛啊。。

#9

HJin2007-07-31 11:44

That is coolest code for this problem. Would you explain the math? It seems to me a lot of combinatorics is going on here.

You don't need the outer loop. One loop is enough.

int chooseKing3(int n, int m)
{
int p=n*m;
while(p>n)
{
p-=n;
p+=(p-1)/(m-1);
}

return p;
}

[此贴子已经被作者于2007-7-31 12:18:51编辑过]

#10

a84517272007-07-31 20:45

刮大风断电了

等下试下

#11

a84517272007-08-01 15:15

以下是引用wtyj112在2007-7-31 10:15:24的发言：

不用循环数组
只要一个数组用一个while语句两个if语句就搞定。
我的代码如下是20个学生数到3就出队列。
#include <stdio.h>

void main ()
{
int stu[20] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19};
int cout = 0;
int cout1 = 3;
int *p = &stu[2];
int pu;

while ( cout <= 20 )
{
if ( cout1 == 3 )
{
cout1 = 0;
pu = p-stu;
printf (" %d ", stu[pu]);
stu[pu] = -1;
}
p = &stu[( ( ( p - stu ) + 1 ) % 20 )];
if (*p != -1)
{
cout = 0;
cout1++;
}
else cout++;
}

}

************************
if (*p != -1)
{
cout = 0;
cout1++;
}
else cout++;
}
***********cout++是什么哇

#12

gzhsea2007-08-01 17:04

以下是引用a8451727在2007-8-1 15:15:54的发言：

************************
if (*p != -1)
{
cout = 0;
cout1++;
}
else cout++;
}
***********cout++是什么哇

赋值后加一

#13

wtyj1122007-08-01 17:27

cout 就是用来纪录已经出数组的空位个数，在我程序里用-1来表示空位，当空位到21的时候就结束程序

#14

wtyj1122007-08-01 17:47

我加点注释 cout就是总长 cout1就是步长

#15

wtyj1122007-08-01 17:57

原先给的代码有个地方有点累赘总看不舒服就改了下顺便加点注释

#include <stdio.h>

void main ()
{
int stu[20] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19};
int cout = 0; //总长
int cout1 = 3; //步长
int *p = &stu[2];

while ( cout <= 20 ) //全部数据出数组了程序结束
{
if ( cout1 == 3 ) //每次指针移动三个非空位置后就出列一个
{
cout1 = 0;
printf (" %d ", *p);
*p = -1;
}
p = &stu[( ( ( p - stu ) + 1 ) % 20 )]; //指针向循环数组后移动一位
if (*p != -1) //记录指针移动跳动了的非空位置数
{
cout = 0;
cout1++;
}
else cout++; // 记录指针移动了的空位置数目。
}

}

#16

blueboy820062007-08-01 18:54

果然都高手，我学了几天C++，还不知道什么是：“循环数组，双向循环链表、

baidu google：约瑟夫环”

伤感啊……
学无止境啊……
埋头苦学去了……

#17

wtyj1122007-08-01 20:29

越看自己的代码越不爽发现很多地方不好就改了下 cout改成了每从数组中出一个数就自减一次
这样代码更好阅读程序速度也比原来快点，思路也更清晰了。。
我太菜了写的代码经不起细敲
#include <stdio.h>

void main ()
{
int stu[20] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19};
int cout = 20, cout1 = 3, *p = &stu[2];

while ( cout >= 1 )
{
if ( cout1 == 3 )
{
cout1 = 0;
printf (" %d ", *p);
*p = -1;
cout--;
}
p = &stu[( ( ( p - stu ) + 1 ) % 20 )];
if (*p != -1)
cout1++;
}

}

#18

a84517272007-08-01 23:01

以下是引用wtyj112在2007-8-1 20:29:43的发言：

越看自己的代码越不爽发现很多地方不好就改了下 cout改成了每从数组中出一个数就自减一次
这样代码更好阅读程序速度也比原来快点，思路也更清晰了。。
我太菜了写的代码经不起细敲

也不错了啊，比我牛多了。

#19

a84517272007-08-01 23:04

先多谢大家，我看下哪看不懂再请教

#20

野比2007-08-02 00:12

那个...站成一圈..用下标求模不就O了? ..
index=count%round...

#21

a84517272007-08-02 11:17

以下是引用野比在2007-8-2 0:12:55的发言：

那个...站成一圈..用下标求模不就O了? ..
index=count%round...

这个。。。不懂

#22

野比2007-08-02 19:46

人员索引=计数%每圈人数
比如每圈4人, 计数从0开始不停增加
则人员索引=0,1,2,3,0,1,2,3,...
用这个去检索数组不是不停的绕圈吗?