鱼C论坛

 找回密码
 立即注册
查看: 3547|回复: 4

猴子问题

[复制链接]
发表于 2011-10-2 03:45:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
大家好!
/ _/ f3 b+ Y9 v" w& S这几天我在忙着编一个问题,我用了一种方法编出来!( N1 ]3 w& ^: q
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
# ^$ v; n' \% C4 Y5 _5 T0 ^& g注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
  g- k9 Z( @& c* H  v& {5 _( z0 N% W* ^0 D* U# L
, q% b  F& S* Q; q3 N) ~
                            题目4 g+ p1 ^( h0 f- P+ a
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
6 ^& @" _8 ?+ a, O  \第一种方法:利用循环链表
8 s, h8 R7 A6 T/ D) o5 e7 O#include<stdio.h>
/ \" A$ o4 S8 C* ?4 H" b8 S#include<malloc.h>% I0 B+ ]$ E% e
#define M 8            //共有8只猴子/ G8 e8 s( @3 \; b9 T
#define N 3            //数到3只时退出第三只8 g2 U/ s8 N* f$ q
typedef struct monkey. I5 P8 {9 _! d& U( n" W7 [
{int number;
9 R0 Y7 d! c1 {. Mint flag;
+ {7 L5 {* F  e' E" [! x! fstruct monkey* next;
4 ?# f8 i8 m; ^}MONKEY;' i. Z! k9 r$ I6 v
main()9 K' r7 C" K" u; R1 M- `
{ MONKEY *head=NULL,*p,*s;
# E% o4 d* _" L- R5 a' Y  int i,sum=0,count=0;
8 x5 c  m; Z& L: r; J  clrscr();              //清屏
+ U& P! A2 R' C$ @/ L3 h% D$ e  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存  X- S- e3 J- Y$ n: i
  p->number=1;p->flag=1;
; B  O: Z8 z5 M2 g- B! d  p->next=head;2 a+ \/ G7 \! b$ F# I
  head=p;
/ h2 r+ O# D1 G5 N3 k1 c* ^7 {# \  for(i=2;i<=M;i++)
' g' `/ N7 \" @( O    { s=(MONKEY *)malloc(sizeof(MONKEY));' ^( Z& `* r, b: }+ p/ S/ t2 D7 N
     s->number=i;s->flag=1;# M! ~" ^6 c( ^) q. r
     s->next=head;" c# w0 V* O) \) E
     p->next=s;p=p->next;) C# \: _# u2 V' Z
    }
- \3 n: |! T- m8 i9 r    p=head;
. m- l) d  _2 F* q' G   for(;;). A0 n+ s/ U8 b) C  x
    {if(p->flag==1)/ Z1 X7 m2 W( x$ \0 a. W; N1 ~
       count++;1 j) @, K$ U, t$ P" L
     if(count==N)
1 N5 M/ N/ q, Z; S& j0 Y4 n        {p->flag=0;' I! h. s! Z$ p6 c0 y* E- k
         count=0;
* h( L1 g/ D! a5 @4 o2 T! X. h         sum++;}
7 x  ~3 H1 }$ R4 i     if(sum==M-1)" f. F9 {  J" c9 Z
        break;/ M+ q1 j% P( S0 h$ J" f, o6 W% h
     p=p->next;# [3 E9 r, f# G- V6 r
    }
  O) G4 L7 ^# c7 l    p=' v$ U& m% A. t. h2 K$ U- m. ]
    head;
$ k/ v4 o8 R: D1 d    for(i=1;i<=M;i++)/ _7 X2 Z7 d- s. q: t
    { if(p->flag==1)6 A* i3 u1 a: {) T9 |6 f
        printf("\t%d",p->number);( G2 g& X7 I# M
      p=p->next;/ g( y" N9 n6 {0 k
    }& T% y6 F2 [$ D$ ]+ b) S
- d1 n# A4 l+ t& @# i
6 V& V% h' z; R( y* X2 l+ {

+ h, J& {4 k, l/ x}
  }$ P# w% I9 d. E- t- I# Q* ?
第二种方法:数组% B$ o6 Q- a6 ]) e
#include<stdio.h>' `$ z5 W( J& H: z6 D) {
#define M 8
/ C6 O  R$ Y6 V/ T2 }struct monkey
2 o5 E/ n& C! g. P" t- X6 U+ ^8 W{int number;
, |/ k9 l6 H' M' a( Y# r0 b3 K" Q0 ^int nextp;
5 J2 z, [+ F, H# t4 e* C3 @$ N}link[M+1];
2 L. v  F9 {0 d7 o/ x* S; `: T6 \+ v. d6 _' H  @
void main()4 i& Y# F: g0 t
{int i,count,h;
3 ^# e0 o1 ?: f8 F* H1 A4 Q1 }7 ^6 rfor(i=1;i<=M;i++)9 x: i+ \! @) f
{  if(i==M)
! W5 w8 P, ?& ~   link[i].nextp=1;' ]) o3 _3 s# O. K% c1 v8 k
   else
9 l( D$ U4 B' w7 a3 m   link[i].nextp=i+1;8 k* c( X* |6 e
  link[i].number=i;9 U  P/ v4 o3 K9 k0 X& [
}4 G. ^2 P4 G" `/ s! V
printf("\n");3 ?: B7 M9 F) e7 P3 k' A
count=0;, E6 r0 @1 W8 `. [4 X) E
h=M;
% `& H' p. v8 X( ~printf("依次退出的猴子: \n");
3 s& J  f1 ]0 k# t2 O* I0 qwhile(count<M-1)# h0 q- N1 `. w* F
{i=0;- s/ H; U/ {( U
while(i!=3)
; L- k( k" {# S8 z{ h=link[h].nextp;
, |5 R8 k& A1 d( V0 ~% D. v0 W2 I   if(link[h].number)4 J  P2 k; {, r
     i++;}8 |" ]! x) g& I. j
& Q4 ^1 m8 M% j9 {. y
printf("%4d",link[h].number);
+ ]* P3 T# l3 B6 ]% }1 plink[h].number=0;0 }! A* X6 G% ]5 d" L, [6 v+ [2 v: n
count++;
1 i9 V7 T9 Y1 f- ]$ Z: E}
! D! j0 L8 ?# U2 R2 o, Y0 i9 u" B! R/ @; @* c: J; u
printf("\n大王是:");6 v: W/ I5 u, A, }7 ]+ `
  for(i=1;i<=M;i++)3 H& ]3 E# L0 d) {6 V; y
  if(link[i].number)0 \) n6 I0 m. D0 Y. P9 _
    printf("%3d\n",link[i].number);" q$ y- T4 `: I* ~0 f$ Q

2 o" H2 M' m5 Z1 w
$ Y( b7 ~' W) |$ d& Z- ~0 M: _; E}

! _; R: x. ~$ m( _( n. |* c* n* J# Q第三种是普通方法for循环
# N. [* O% a/ }
#include<stdio.h>& e: N) ?# l/ L8 i+ [
void main()/ ~$ g, J: {3 C- m- ^* G" J, a/ C7 _
{ int i,k,m,n,num[50],q,*p;
4 W' e1 S0 R/ g& Y    clrscr();9 g& I: S  Y, ^9 s1 ?- m
   printf("input number of person: n=");! Z) G. Z, s: W  l
    scanf("%d",&n);
, h/ e3 ^7 a" k' f3 Eprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- j1 x+ m' V9 @4 ~. V- \    scanf("%d",&q);1 w0 V6 K$ Y4 D5 U& S) |
   p=num;
5 b, I& D; |1 P  for(i=0;i<n;i++)
4 w4 D/ |( @1 k  P9 f/ n( s    *(p+i)=i+1;
8 k2 D; \; p1 G- D8 W   i=0;& }4 O5 t) d0 f1 Q7 d
   k=0;+ I4 C2 a: }1 v7 w' }
   m=0;
" P% R  I6 f/ `% A* {4 {  while(m<n-1), B; x3 b- K, E5 G* I
   {if(*(p+i)!=0) k++;
& o# y" [$ r8 t+ a0 s1 ^- x3 P4 c     if(k==q)( I3 ~4 v! Q; C: Y# b
      { *(p+i)=0;# A  a: c1 q6 F9 n, y6 v4 ]5 q
        k=0;
4 p: w$ r/ Z" p/ t3 y  N' N9 M        m++;5 A2 s, s. E4 R/ ?4 k1 I
      }- I+ K. g% X( w8 P
    i++;
# e* {$ U5 ]: J, {! B7 E, i1 m    if(i==n)i=0;
" N' B! c  l8 i; V3 K" e4 _   }
" p9 M1 U" F, z% H3 k: {- S9 K. h* B+ y" P  while(*p==0)p++;7 L: P" S4 \* \
    printf("The last one is NO:%d\n",*p);
9 t4 {8 N' l+ r  L7 Q     getch();. j. X1 ]; }' c

# z- _* u) S+ U}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;- G0 p* I( [7 C4 C' Z. |* Z
namespace 又费马达又费电3 U: j' h/ {2 `7 y9 q) ^, X
{, T+ b; j5 D/ G* W+ i
    class Program
' N5 R: \4 `& _3 |9 ~* W    {# X, i3 y# B+ a4 z! M. b8 N
        static void Main(string[] args)- z1 I* m) u# g, g  ^) Q
        {, c& H# p3 H8 f
            int m, n;1 d6 A' w6 _  X2 q8 N
            Console.WriteLine("请输入数组长度");& y9 A2 ~- m; M: ?% P' k
            m = int.Parse(Console.ReadLine());//m为数组的大小
* ?- X6 F1 s: S3 o' F            Console.WriteLine("请输入要截取数字的大小");
- T& A, F8 l0 `% L            n = int.Parse(Console.ReadLine());% z5 c# L2 j) P% E  {6 n
            int [] numw=new int
9 T/ J: D( S. |  h7 x& Q' A. v* y* {3 I* M6 u: U
&shy;&shy;&shy;;
: c. O  A. v% ]) p            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
# m  C. z" Z+ t/ Q            {' m" s# }+ w1 @; F' ?8 U
                numw[j - 1] = j;
  _" T4 M. W, i/ f' ?5 O1 P" Q            }! ]. \( x, V+ n& Z. D- D/ _/ x
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
- ?; L4 G+ g- B% n! t, @            while (d != m - 1): s$ t, N+ D6 a/ x- q
            {! A4 H( v$ D) {1 Q
                if (i == m && d != m - 1)
2 l) O% I& |* t1 O* D                {: I! H) t6 N: {  d/ o: C# q0 {  o
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!3 M- L" s$ `+ d" l. W
                    continue;6 y6 d! n. X& E; K
                }; h* j5 n0 Z$ c
                else/ f. ^0 c9 _/ {$ `9 `$ H
                {- v# b7 L  {& S
                    if (numw[i] != 0)
# {5 ~" A5 |" F+ m3 Z+ ~, S7 ]                    {
* C0 [: V- [& T4 ~0 r8 J                        i++;
& x- Z7 X2 n. Q  {1 N                        k++;
7 N& C6 h$ I  x- q/ u                        if (k == n)
) c3 y& p6 U' T+ e1 `                        {* y- t" ], W' \* C" V* {- _
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
- i) p1 }' F9 l. X+ L                            k = 0;
# ]0 q. z% G# _5 v/ p/ x, Z/ x              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
* {  w/ R& X9 o, o1 M* c- Y                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 R7 o5 c. i. |/ |; ~
                        }1 ~" B, [$ b8 r. x0 J( g3 K$ |  W9 s! t
                        else//输出暂时还没有改变数组元素的值
9 B4 D- k" f; a  a" Q& b; D, W                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: D3 _' _8 a$ r" t6 A! d
                    }6 S4 k5 v1 y* i- ~/ P9 K
                    else
( v' {( r1 X# |# f0 A+ H+ Q3 V                        i++;//数组元素为0,直接跳过,不计数。。。8 f1 N! @* D2 R/ @
                }
+ W; g( u5 m  s, h# x 6 [% X2 D: c, g) q2 d
  D$ I4 V/ |& P0 P. Z' ^5 J5 m) y
            }//结束while循环
6 H) ?2 u! j: j; g& }5 x            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
  @& p# |4 L" K9 n           
% {: \" J  U- P" z# c                if (numw[i] != 0)8 @5 ~& `$ C9 K0 `, x5 u
                    Console.WriteLine(numw[i]);
! ]  j: ?6 I( J  d+ u, n           
! T1 G2 E5 W* I4 p- f            Console.ReadLine();$ l3 k5 m( ?( ~6 A9 p7 H
        }
3 ?" c2 L' T: N    }
& N2 m+ S1 u3 ]' G$ ?; ^& [" t( P}
' E5 O9 o/ Z5 L$ i  [* h' h
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
小甲鱼最新课程 -> https://ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2026-2-21 11:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表