鱼C论坛

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

猴子问题

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

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

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

x
大家好!
9 o5 q5 V1 F( f8 l* \+ }/ N2 f7 n这几天我在忙着编一个问题,我用了一种方法编出来!
. j/ n+ n* O; |, c: \/ t, s但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
9 S7 G- u9 b9 A$ U0 \, D. x注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 , ?2 `9 f6 |; O5 Q
% R  C3 x* P2 v0 l: \9 `
1 l3 Y) Z1 M5 X$ W' I
                            题目
* O9 o# g& H0 W2 f山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。' S5 L& l3 \1 J, L9 w$ \+ B8 b3 m
第一种方法:利用循环链表% ], E- S, b8 \0 N7 q
#include<stdio.h>
* `7 j' \; F8 S1 _! t5 N$ M# C8 `#include<malloc.h>* w" y% l0 G  Y2 v& Q, m, u
#define M 8            //共有8只猴子3 j1 _& J, m1 Q8 o; v
#define N 3            //数到3只时退出第三只
& P: g1 J" `  c# c! ntypedef struct monkey
- V  ?. R! \9 ?6 Y# s{int number;4 q$ v$ p& z5 [- J
int flag;
/ J5 [$ ?) |) \4 b8 `8 Vstruct monkey* next;: e: p) _+ ?( x6 `3 _1 B
}MONKEY;
$ L+ J/ Y" X( K0 D# `, Gmain()# b$ }) O: i, x1 H; `
{ MONKEY *head=NULL,*p,*s;! K" t& y, W1 U8 q  K
  int i,sum=0,count=0;
+ D1 \) E* E& Z/ f  clrscr();              //清屏8 ~* J" W5 L2 k  ]! Y( ]
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
# p- c, s& h( M8 {/ }- \) p  p->number=1;p->flag=1;
- N0 u, J3 Y: T! w  p->next=head;+ ~6 h( V) A. p6 L0 g: e  l4 M
  head=p;- r! s7 d- U- Q9 _" R
  for(i=2;i<=M;i++)
) G3 p/ q7 i! A+ E1 M% r' t& X    { s=(MONKEY *)malloc(sizeof(MONKEY));
& Q9 U3 {8 R" i* u1 W$ p* U     s->number=i;s->flag=1;7 g4 [# ]9 c( o- b8 |, e! C: l
     s->next=head;* L% A* M  G, `1 B  N" F
     p->next=s;p=p->next;
7 q) W8 p- F2 h. K$ {    }
, D# Z8 g3 D2 ^7 u8 `    p=head;# J6 m6 T$ p8 A
   for(;;)
# y7 b* l! Z2 s& g, ?8 F2 I    {if(p->flag==1)
# X2 R' J3 Y$ P* y  `+ a3 z2 f3 ]' ]% G0 F       count++;
8 d3 Y1 D4 L: b( d     if(count==N): @' p* p: {" s% O8 h
        {p->flag=0;* P" l* {# h/ ?1 ~5 d; b
         count=0;" ~: u9 c1 N6 h, A& x1 x
         sum++;}* ]9 W0 L7 U' A: I/ p
     if(sum==M-1). u. d3 V8 g  b6 B: v
        break;' z  n. \0 g& b! L: E( s
     p=p->next;
- M  R9 |0 D+ A    }
4 B2 c) X0 ^8 s1 z  N3 {  `4 b    p=" T, O1 C  s! U; P( f; U/ e$ B% G! p. ~
    head;
$ ]9 I  k5 G# |, P    for(i=1;i<=M;i++)
6 V; h% V$ }3 q2 Y9 ^    { if(p->flag==1)
( Q. [1 ^: Q1 o' |        printf("\t%d",p->number);8 P9 Z& P7 g: G  E
      p=p->next;0 q3 B4 {% E3 N% n# n
    }' w, g5 R, V, j2 }/ a1 i
+ G( G! U4 X6 _, j$ M
3 F! m/ n, q$ q( o

% W" J% w+ R) G3 U}
8 J) b/ D; L. a+ R" h# V# ^' C1 C2 u' g
第二种方法:数组
* c  L: G& H" X, I1 G7 f#include<stdio.h>. }; x0 J+ s. @7 g2 p: F, ~
#define M 8( C7 a' X' e: ?) X# Q
struct monkey/ f; Q, ]; ^/ y7 s) f/ f
{int number;3 U8 [: M+ f1 V# n1 I6 t, P
int nextp;
. x4 Q- F; {. I+ ^% `, |}link[M+1];
) _5 Y6 X  a6 b: p* M( q9 b! L$ [4 C6 r; E7 m
void main()
1 Y0 r* c0 \( c2 _  ?8 E& Z& s{int i,count,h;4 T# ]! {- V- e' F7 A
for(i=1;i<=M;i++)( _( U% @" U- D
{  if(i==M)
2 S- U) N/ D5 N# n1 q  A. X: C   link[i].nextp=1;/ k- t+ e/ A& O6 X
   else
2 m) L  p4 d: O$ a2 O; S1 h! m   link[i].nextp=i+1;; k* |4 j& ~, Q
  link[i].number=i;
3 d4 f* t( G+ x) ?' J! q! t% {}
. i& _0 J( U! D- V0 G1 \! Aprintf("\n");( k3 X; S* `9 ]* z4 [6 [5 _% f
count=0;. s" {$ I0 _2 Z$ }6 x" Z
h=M;2 `! }& N0 g2 b* j5 Z5 V
printf("依次退出的猴子: \n");
, h. V* G8 b# r) I1 n* m( @) e$ xwhile(count<M-1)) @2 {- l& N, R! L  P
{i=0;
* h$ V" W8 _8 U8 h3 p; z. Gwhile(i!=3)- \0 s3 i: X, {* b% B
{ h=link[h].nextp;
1 W% j& k$ u$ h1 R   if(link[h].number): c& i4 O" G8 f3 H& J
     i++;}4 q5 n9 S/ t9 s' J. ]

$ f  Z: X! `3 W; |$ Jprintf("%4d",link[h].number);
$ X2 @- u7 o- t. v2 ~: Q' d5 Mlink[h].number=0;
( t  P% `! p+ X! Y4 C# H4 Dcount++;
8 d) I; Q$ L$ M& S+ h}
& W4 t7 {! e% l& `6 j& @* K' C- Q2 w* I5 m; \5 i  \! Z( A
printf("\n大王是:");
3 h! ~! i/ M8 M/ W  for(i=1;i<=M;i++)
# u9 b8 E! _6 V" I" {  if(link[i].number)
0 u+ w# U0 x' G2 }& V3 ]    printf("%3d\n",link[i].number);3 A' \% [9 ~% ^

  y3 [# Y6 b! K9 |/ J3 u
" B) l4 j  o& X8 C# O7 e}

- t" _0 ^- `* C" a* S. |1 j第三种是普通方法for循环

/ {7 B  \2 M& Q$ E; g3 ]' g#include<stdio.h>
; ?+ {6 b" A8 X" _# `2 t2 zvoid main()
2 l" o4 V* _( g  V* a. H{ int i,k,m,n,num[50],q,*p;9 I5 N1 M* Q4 u5 @+ K
    clrscr();! b. y" }4 k9 U& r0 ~( w3 i
   printf("input number of person: n=");
7 F! `7 L. _8 @: W    scanf("%d",&n);9 r, \% w+ F6 G' I  \% N
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只  [) b2 K; C1 w0 l8 E: @, x' M- L
    scanf("%d",&q);
9 Z+ n) o6 f; U; Q$ L) C   p=num;( d, l% A, a) O1 z5 a2 E0 R$ r
  for(i=0;i<n;i++)
! X* o. R! [  y8 ^" `* _8 _/ w& S    *(p+i)=i+1;8 V# s; H8 q0 \4 d- ]
   i=0;
! L  i1 x/ \$ C   k=0;
6 @  `7 E  ?7 y   m=0;- L+ m! H9 W8 m  L6 ^$ a
  while(m<n-1)
7 ?+ F& g+ I. P$ q   {if(*(p+i)!=0) k++;! [) [" A3 R( n
     if(k==q)
5 ]6 m$ R* D/ u      { *(p+i)=0;
% ?4 t0 O8 ?6 p' G        k=0;$ a% V5 E" Q/ M2 s6 |! K
        m++;
8 y* o" W8 Y/ _$ o8 C      }2 V; }# f! p) M' q8 R0 ~
    i++;: \/ B5 S9 g6 m7 F' f
    if(i==n)i=0;$ k8 S: Y$ B# b
   }8 Y" K! q2 A/ V
  while(*p==0)p++;
- G2 l5 G% y3 Z    printf("The last one is NO:%d\n",*p);
  r4 ]# d5 _: M& n+ o9 U     getch();
: S1 f- R; m( O2 ^, R2 K. _  \3 y, T! M' y; j/ l
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; N/ u( x2 t# g4 P7 ynamespace 又费马达又费电
4 p& E: s4 e( y4 N- Y{5 E) u" Z! }2 b8 `: I
    class Program
! U* j* e- v# O! y1 R5 J" b    {0 c& h* P/ o7 {' e$ ]
        static void Main(string[] args)
( T2 W4 \$ S: f. E6 J9 D        {
8 C6 [9 j8 W' ^/ n; ?& m            int m, n;* B9 E; m5 s; t; F6 S' S$ q% R
            Console.WriteLine("请输入数组长度");
% \  }- N  d8 Z  D; V            m = int.Parse(Console.ReadLine());//m为数组的大小
; j  z3 L, u; O9 M  u5 j& z5 w0 s            Console.WriteLine("请输入要截取数字的大小");* G7 R7 g! O2 v! J
            n = int.Parse(Console.ReadLine());4 D5 m0 i! S2 v& K( t9 v! n6 e: Q
            int [] numw=new int) l! x+ l6 I- S& l8 O- O+ n2 N8 m0 P

3 P* M2 V! N; ]! _/ O4 _/ K: L&shy;&shy;&shy;;
! V7 D* M  s1 |! s. v2 s+ F+ h            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 R. ?6 f* B9 t* D  f& k
            {
! j' ^/ F0 O! }' j* z                numw[j - 1] = j;
! z; r( l" C9 d1 t            }
6 a. [! f/ C. v            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
! t8 f# b  z8 e& g$ g' x+ C            while (d != m - 1)
+ a4 R9 B8 v8 u6 h            {% C4 K; L" A  Q9 U% f' f
                if (i == m && d != m - 1), T* ]" t5 l1 p3 Z, T/ @
                {2 k" q- ?3 h$ q% a4 v* d; r; T
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
# _, P" @: W( q+ Y7 f                    continue;
8 z7 x# Y% |. D6 Q+ T                }& k! D& w& K7 Q5 [$ e# n" Q
                else
' i1 J$ c) Z# w8 s9 m                {6 K/ J3 f1 P1 A- D  E) R5 h" y
                    if (numw[i] != 0)4 W6 v  @$ n) ?! y$ J3 v
                    {
& q2 w$ }' }8 z6 r                        i++;
" {1 O: ?; u+ P9 T# e                        k++;
/ K- ~) P9 A! t3 [# _' L- B  X; Y                        if (k == n)  N8 c) [+ k8 B+ k
                        {7 E1 ?& |( \6 k" i$ {
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
, R- [1 O2 h& `                            k = 0;
% \- \( {" U* l/ b9 C6 L              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
  h' x9 N0 ?3 s/ J/ h5 S                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
  r6 J+ P7 ?% T6 H. e! u* O                        }
. y0 O6 O, L0 b( W' z                        else//输出暂时还没有改变数组元素的值7 }) R& @* r, c, i, R1 O1 [
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
* Y+ N& o3 o; u+ ]! E. [. k1 H7 h* w                    }8 j+ B7 M7 b1 g1 Y7 o! L% m
                    else
: D5 Y' _/ e, ~4 w6 X# m- U7 ]                        i++;//数组元素为0,直接跳过,不计数。。。
: \! _" ]4 O# O1 ]1 v. ^9 p3 N                }
" P& k6 B: G: @9 m! T
" f. r. d- G$ o1 I1 N2 v0 J, j$ t% N
            }//结束while循环
; T' ?8 \" E" L+ ]* r            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
; d( v; U1 c+ e           
) c" J4 Z5 p/ s$ N; F                if (numw[i] != 0)+ y% O, b$ j3 b* d
                    Console.WriteLine(numw[i]);4 a! o9 k7 R3 X* v/ L
           
; ^3 f$ F  z: q+ n: @            Console.ReadLine();
8 A6 A  ~  k! A. D$ d  }" g9 k, k        }, v9 p5 }% ~2 ]# Z+ J6 l
    }
) c$ g. v  Y4 h" N1 N: B: ?  e7 V( b}" q* K0 u  B+ u6 b& B+ ~
小甲鱼最新课程 -> 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-11 23:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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