鱼C论坛

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

猴子问题

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

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

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

x
大家好!
! G! h6 P' r* p3 [- Q这几天我在忙着编一个问题,我用了一种方法编出来!
3 _) B  c/ [2 j但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
# A2 P9 \4 A  m8 |注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 6 [6 F1 w/ ~: p9 E1 _9 g+ y3 Z
/ k; O9 I9 ~; S! d  V" d$ I$ H
) |' V+ Q9 u) _1 {: P
                            题目/ \# ?- [% T+ O6 V; g
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
0 ?. A+ Z  ^/ h+ ~8 g" N第一种方法:利用循环链表
2 {" w5 M% ^* t( I5 @#include<stdio.h>* B, m& F) b4 L# k
#include<malloc.h>, \: m8 X5 _+ M& d$ Q
#define M 8            //共有8只猴子3 q# o& J- ^1 f
#define N 3            //数到3只时退出第三只) x+ k$ ]; k- Q& e7 g# e
typedef struct monkey) y2 Q/ Z! E9 d! ~2 L1 C
{int number;
& ^  Y- p) a; s2 i1 n( z: lint flag;
: G9 l+ \7 H2 r$ w4 Ostruct monkey* next;
0 I, D  V* a! _% e* \}MONKEY;
+ v9 Q! [$ u" a& [; Omain()- ]! i! [0 I2 i+ `4 e
{ MONKEY *head=NULL,*p,*s;' D' [; [1 S: V1 e/ W1 B
  int i,sum=0,count=0;
  |+ d" B, d; h  clrscr();              //清屏! v, x7 ]% u+ ], |
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ h; `$ O4 [' m" h" a; Q
  p->number=1;p->flag=1;& W. Z' l" l( {, q  b* U% B% `" `" v
  p->next=head;
7 v( n2 M' `3 |# K2 E. T0 j  head=p;
" |( p( d$ F& R; j) r  for(i=2;i<=M;i++)- z$ Q2 C' r9 Q, d6 x* P* T* \' u
    { s=(MONKEY *)malloc(sizeof(MONKEY));
) |* J5 N& X5 y$ @     s->number=i;s->flag=1;
- w0 M) N1 y1 b% E8 A8 P     s->next=head;" d# y! k. n% Y4 B1 I, _$ X4 [5 a9 {
     p->next=s;p=p->next;8 M3 L. p4 S) c# x6 o5 R
    }
; W( S& ~) Q7 M& \; U    p=head;
' e7 J4 S" P9 U- ~# `   for(;;)! x# f# y! ^3 ?$ o0 o
    {if(p->flag==1)
- @( l9 G' U3 O+ E9 L1 H) P  N       count++;
$ b3 M, G4 B( n" ~; O% U     if(count==N)
3 L3 T, w  O; k        {p->flag=0;
% L8 Y, e3 N1 z, |; G6 O         count=0;" u  F# w1 E* P- J3 m
         sum++;}
: k. Y" }* A2 ]' J* a# a     if(sum==M-1)
* B! u7 X; z: @9 {( ^$ |        break;
9 f/ n) K4 W% L, ]3 b" Z     p=p->next;
- r5 \  U" p1 p, z    }
% I, K8 u/ N9 D' L    p=2 V0 y% U/ L& S8 c+ b
    head;2 y, r! h  f$ L) T+ C
    for(i=1;i<=M;i++)  O+ T" {' N2 @
    { if(p->flag==1)
- N( `( `- m* o/ I7 W        printf("\t%d",p->number);0 I# H, @5 l* s* u! g
      p=p->next;
0 h' k& {3 D' s9 g3 l7 _" a" W    }
6 h. r* r, m+ S' q
4 K- K" D, S1 R, {7 o4 V* v. `1 g. I3 P

0 W7 J9 u, ^2 I' T% k}
8 X5 E2 L# @. Z6 L
第二种方法:数组: u% e) f* G* K9 u$ z! j' U
#include<stdio.h>
+ w/ v  s- `: U' H/ Z4 {#define M 8: |7 V& a, O* {+ E+ A  q; f0 [
struct monkey
; a' |8 [9 e$ p6 i  o: Z* b{int number;
" B. |  Y8 O5 h) y$ iint nextp;
' X7 d" v# t2 L! u$ K9 w4 t}link[M+1];6 N  C. r& x( D! |3 L7 L3 ?

" G  S' n# N8 I6 ~2 n  M0 Cvoid main()2 @2 L0 W0 _* F5 R9 H0 V$ x6 p
{int i,count,h;- R3 \5 E1 T9 I6 S$ W+ Z
for(i=1;i<=M;i++)
2 W$ c: {3 a7 Z{  if(i==M)0 Y" i9 Q2 D1 F, d' ^
   link[i].nextp=1;
( Q# q/ G: e  \' ?   else
* _$ i& }! z5 S' S/ Y5 l% e5 H   link[i].nextp=i+1;7 L2 ?  \- B0 q% e2 q
  link[i].number=i;+ r& h. _6 y5 h
}
3 G3 a* G  v& \( V+ zprintf("\n");% ^! t% J& A) S1 K
count=0;) ~5 n7 J. {9 f$ ]: }* d- X
h=M;
3 X- G1 P" Q1 A: H: O* |) Zprintf("依次退出的猴子: \n");
. S. s6 x+ N3 R& m7 Hwhile(count<M-1)& R: x/ |4 s: H" l$ o1 S5 h
{i=0;  Q; T: @1 F0 L6 B
while(i!=3), f9 m7 a7 k) e  B
{ h=link[h].nextp;
6 d8 d" o. f: Z   if(link[h].number)1 P% Y& P2 ]( ^0 ]6 }5 y# a' u. |, p
     i++;}
( q1 O' K' e4 c: v1 s
2 F4 Z. z$ q: [" p& b# Cprintf("%4d",link[h].number);
9 [: V' C: x* @* blink[h].number=0;1 R# L# o% @( K& k
count++;& i% B( z: P. E. k' L' H- }' c& n' O
}
) f+ Q" B; w) F1 w3 B2 v  c& H4 Z6 ?5 ?, }
printf("\n大王是:");. v3 O3 N9 L9 i' z% A( M
  for(i=1;i<=M;i++)
" u7 H! r* B# z9 j0 A- f( ]: K& `  if(link[i].number), `0 P! p2 L8 B: E4 D
    printf("%3d\n",link[i].number);- X8 O; G9 E" Q
# p  C/ S8 o) Z% u) \
- y5 S, U8 `. K2 K
}
" M8 G2 D" S3 z) N1 l8 u6 K2 ?
第三种是普通方法for循环
4 ?2 F& ]# ]5 T' R
#include<stdio.h>& ?2 I7 S0 G$ n8 s; s* L/ D
void main()* o7 k+ M  A7 x* e" [7 R
{ int i,k,m,n,num[50],q,*p;. \9 W  D' V  X7 M
    clrscr();
6 k: F8 n. V$ ^   printf("input number of person: n=");" K5 L2 p" C3 ]) b; U# n$ j# i
    scanf("%d",&n);! @4 B5 c+ p, C
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- P: n9 D. u3 }. r    scanf("%d",&q);2 C5 N% {" Y8 N
   p=num;
  N2 Z3 K- v: r) Z7 s  for(i=0;i<n;i++)* L. I. t# {3 p
    *(p+i)=i+1;
  l8 A( X3 m+ o; ^: h  M1 R  s   i=0;9 a. y1 a# v7 _2 W5 P4 U
   k=0;- k2 J; b/ P  `' {: S4 e
   m=0;" K+ l$ l' W' f% b5 l
  while(m<n-1)
) D) k% C7 T4 g2 D# t$ S   {if(*(p+i)!=0) k++;
/ E% E' C) l, n1 E& _9 w3 i: v     if(k==q)
' z/ z# |2 q! b* U1 H      { *(p+i)=0;" t8 m# \8 j* W# u
        k=0;
. L4 w6 q1 Y3 m8 _, `        m++;  \) h8 f5 r- \2 ?, l7 R
      }2 y! w0 l6 j: P  h
    i++;8 T, ^! X" Y7 s4 @3 k
    if(i==n)i=0;% j# P1 E% ~' p0 H2 W. O
   }% }- b/ K5 V7 A+ T4 D7 y) I
  while(*p==0)p++;: C6 ~" B9 X; T- m8 r- o
    printf("The last one is NO:%d\n",*p);' L" c1 \) H% k  @8 O
     getch();
7 C3 w5 {9 g) x4 V7 z2 }7 C- B2 `% \
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;9 j- `$ u- `! \3 K0 W- x  D
namespace 又费马达又费电+ _* H3 F; }9 \/ Z$ g
{" o( E; h" Z4 I. x+ u/ j/ s4 N& E% l/ B
    class Program
9 C  j9 o* t: p    {# E/ W1 Y. [0 G) u9 P( M. W% j
        static void Main(string[] args)
3 J; s6 x2 C4 O- C. [" I        {. F0 {2 l5 L( G2 b
            int m, n;
# p* S: E9 m$ C7 k# ^            Console.WriteLine("请输入数组长度");1 O5 f% A/ f. N* y, m. T* D6 {
            m = int.Parse(Console.ReadLine());//m为数组的大小
1 i+ Q3 x1 s! a0 N; J6 C# [            Console.WriteLine("请输入要截取数字的大小");; w6 z. H5 |$ Z. U! J& e9 v: K
            n = int.Parse(Console.ReadLine());/ \5 t  j- n6 l6 |
            int [] numw=new int1 p0 W9 e# b2 D+ ]
/ H) Q) q' `1 ^$ j# p
&shy;&shy;&shy;;
, r/ p" J, a5 p, R1 K1 ^( x            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
2 `+ R) U. u( i( J8 Q: F            {3 }& \. }# m$ x7 m5 a
                numw[j - 1] = j;* A+ T- U6 K' Q+ ]' m! J
            }0 ?2 d! ~. C" ~
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
& f. z' t' t9 p            while (d != m - 1)
7 U$ N  H0 N1 L8 b            {
& W* A0 M2 j2 _7 }                if (i == m && d != m - 1)8 `& B3 F( H$ h+ E, S
                {( c( _- \7 W+ C. ~( W
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!4 M$ P; C  S+ z3 q. u! W
                    continue;- U8 e0 }$ i0 O: ]6 U) d) X
                }
1 T0 O# n8 U3 z. o+ q: v                else
  d  F, n' O* m, D! T- e9 r+ i/ Y9 e0 o                {
  a3 ]8 j- H" L, X1 i0 e/ K                    if (numw[i] != 0)- Y4 c1 \/ C  S, z  e0 s1 w1 H  f) i
                    {8 n* U6 a7 r. g) }* C
                        i++;
: a! b2 |, {3 R! }. r# B5 Z( s                        k++;8 ]7 [* {' X, y% |
                        if (k == n)
& A6 g  _/ B" v, @9 ?                        {# Y4 G7 `) O+ G) s: e
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& d0 n, O+ `% g7 R' h9 m
                            k = 0;
% i9 v9 k2 J+ k+ I+ L7 {5 [9 ?( v              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
/ ~4 |' F) D  K$ s5 ~) U                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
9 X; F1 B/ @- r# _8 y                        }3 B; r; M) E+ C3 N$ K3 s
                        else//输出暂时还没有改变数组元素的值' B5 k5 j: o( K
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);! s" l% ~3 K0 H& `: Z- m
                    }
0 N+ D* ]6 i$ @5 O& T" X, ~) S                    else7 S3 d4 C4 A# z5 j" |
                        i++;//数组元素为0,直接跳过,不计数。。。6 [  m; B7 O1 D
                }
! }4 E' V( r* ~2 g! S ) P( y8 C4 h+ y$ U; u

& E9 V, Y& j& b: {$ |" ~            }//结束while循环, L# `# `; h1 Z7 K
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
1 K% T1 S7 p6 F  A' R           
4 W' K, D! o' A% U                if (numw[i] != 0)
/ W6 G- ~1 ~3 k& q# A4 ^% \                    Console.WriteLine(numw[i]);1 a# V& {/ L( u
           
9 @& ~, i& h" @' O+ s            Console.ReadLine();
' Y& S3 z4 |0 \        }
  M7 E9 h- ^" Y" M& e1 E    }
% @" d- y* P# a' k4 C% H}3 [" ~# c$ I' n. O5 `  K5 h# q6 w
小甲鱼最新课程 -> 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-17 00:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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