鱼C论坛

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

猴子问题

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

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

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

x
大家好!
0 `9 M' z: Q& W2 k# `* i/ n& y这几天我在忙着编一个问题,我用了一种方法编出来!
& F% h+ @  B( G但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!5 ]9 y7 h! z- d2 z( z9 v( {+ n
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
' u' I( x2 M! k1 p" C  T& n/ [* z4 Y% m2 \& K  f3 q& d; ?
. G) z* ~9 b3 l
                            题目4 b5 m1 ?) F5 j7 V, n
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 g0 R& r' g% `4 b7 w第一种方法:利用循环链表
1 i. }6 J! _! g' A$ L, l; v#include<stdio.h>! n) A1 @3 x0 T
#include<malloc.h>3 `2 @  q  J, K
#define M 8            //共有8只猴子: i- S& F0 j6 H) V7 Z# w, ?
#define N 3            //数到3只时退出第三只
& E: k" ]5 Q3 T$ Stypedef struct monkey/ A$ O# H9 w6 F2 b  ^/ `
{int number;) R/ l" c6 N( Z& x2 D# S
int flag;
7 N8 f" f- l* e9 astruct monkey* next;) K! }& L0 W3 h9 M; D
}MONKEY;9 Y6 D4 O5 l9 t+ ~
main()
- Y& B/ s9 |7 Y{ MONKEY *head=NULL,*p,*s;* F- t! Z3 u5 o) K
  int i,sum=0,count=0;8 P, d1 N/ {7 E; e; d
  clrscr();              //清屏7 E9 {$ j. A; q3 F
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
; B0 y$ C5 }2 I+ j3 H; c2 w/ f) L  p->number=1;p->flag=1;/ y. Y) v& ~) `. I% C
  p->next=head;  V# ^. u: \/ ~* f2 N
  head=p;$ A4 a+ U  e( k* d7 G
  for(i=2;i<=M;i++)
: J7 S9 R" i( \5 S8 v    { s=(MONKEY *)malloc(sizeof(MONKEY));
2 o3 p  T8 }: B0 o2 T; I( S     s->number=i;s->flag=1;& P0 h/ G! A" l* ]7 q- f& W# Y
     s->next=head;# ~2 ?/ n) P- z; V/ Y& W! v
     p->next=s;p=p->next;: E2 D' a, L2 P' p
    }
' K8 r8 ?% T- p, i+ M, s' j/ _    p=head;
. q! q* O2 w/ x% @   for(;;)
1 N4 G+ A. s+ o& G9 B' q    {if(p->flag==1)7 X% L* S. o. I, I8 B: e) e: I/ f
       count++;: b- a& H! a! J4 F, x6 w# {
     if(count==N)
+ L1 f6 V/ e, ^7 K        {p->flag=0;
. y3 [( H1 C2 F0 W3 Z9 w% F         count=0;
. a, [: c( t* q* n/ J4 |: B         sum++;}8 ?# ~8 y5 X; n# D5 j& @( c  S" N
     if(sum==M-1)8 ]8 F: z6 b: U2 p1 G' U
        break;
1 F# P4 X% a" x, G     p=p->next;' S7 r, ?$ P/ D0 w8 o
    }/ }3 b& ~0 |" ]$ R+ S
    p=
3 ?3 P5 T$ W1 ], y- Q4 S5 {. [    head;4 D/ G1 R8 U; I/ n& `
    for(i=1;i<=M;i++)# N9 A) h" J. b3 a  M
    { if(p->flag==1)! L) }- X5 c& s: O, e
        printf("\t%d",p->number);
8 i" l2 |8 y' m9 j      p=p->next;
( j% q; s" C) d9 `    }# X5 v" t: F9 K+ W$ E

$ l- U, O- u. X- U% s8 _: t
$ I+ _$ u; N- ~# }$ s6 D, S4 K* w3 i0 e7 I: W: k) G
}
, u' r; o$ e! y0 Y/ ^
第二种方法:数组4 Y8 b6 l/ a; m6 N5 A, H$ i( F
#include<stdio.h>
+ d' N; Q" k5 q. o! E#define M 8& P) g6 F6 U* Z7 U0 |; @
struct monkey* V: k$ A) t' U: L
{int number;5 u6 _" T# u2 ]4 V' Y0 K5 |
int nextp;
* q; u7 ^- J4 F) N. l  l; p}link[M+1];
. ~4 s# T5 g9 V0 S1 |9 b
+ P1 N  o1 }( ^& `void main()
, h# F' m% v( ]1 h- ?; e) @{int i,count,h;9 i# M& e/ h0 u3 K+ y4 Q; v
for(i=1;i<=M;i++)
% r) W: d# k2 o' C; V, R2 A{  if(i==M); C' y' A7 b9 F7 ~! N4 I- ~
   link[i].nextp=1;
" [+ `- a" r# m! G8 R2 t8 a" N; U   else
+ }7 V* I; ~  `1 n. O, a: g   link[i].nextp=i+1;
. @" R3 D6 k, A/ p6 r  link[i].number=i;
$ V; p- W: X( i( i3 g) z}
) _5 x6 o% Z& G1 P/ Tprintf("\n");2 D: g' A: K/ F& o6 x3 z4 o4 G% R! h
count=0;+ }% N; d! u( J( o2 G. L
h=M;9 i  z3 ]5 e# O) V
printf("依次退出的猴子: \n");# u2 z# Y4 [8 {$ }3 i0 O2 t# f) h1 \
while(count<M-1); r/ F( F+ m, Z+ w
{i=0;
. Z% q) x' P6 Z8 l. twhile(i!=3)8 ~8 y+ ?% s9 g7 F- L3 h( z& _* F
{ h=link[h].nextp;$ m3 u( j4 \. l% [7 m  w
   if(link[h].number)5 ?+ v+ a5 i% J6 w
     i++;}
! \2 f" A( B9 g' h$ X/ \8 j) i2 ?
) v6 [  K# F9 r1 E( Z# Fprintf("%4d",link[h].number);( f# e+ }, ]+ N' Y/ L
link[h].number=0;
- Y$ K* e3 l- [count++;
3 X, j4 d0 Z% d% H' N: J8 v}
* M6 g# E: Z, `9 a; ~) O$ T! x7 D' o5 g& E6 R1 x1 B5 f/ q4 k  V; x
printf("\n大王是:");! o; h0 L3 t: K0 s; r3 c$ h4 f- L
  for(i=1;i<=M;i++)
8 k3 f" b7 n1 y% w' h, S  if(link[i].number)
' u3 n" q) [2 l    printf("%3d\n",link[i].number);
' ~( u, U+ |2 F4 k- x1 I5 @$ m$ \5 a) q  m( ~2 j1 `

8 q- [6 @% Q8 J7 b}
( B& a. c+ R/ {0 C" f* H
第三种是普通方法for循环
3 E8 ]6 z" z, W! v- n
#include<stdio.h>, i2 k+ O9 s0 O  x  X  _5 F; {
void main()
/ z7 f$ K3 q7 W6 ~{ int i,k,m,n,num[50],q,*p;
' k7 \/ F7 V  d3 v5 C8 e, M1 l    clrscr();. J% e' ~0 O- e# ?
   printf("input number of person: n=");5 T6 I% D4 X4 C1 s
    scanf("%d",&n);/ |" e5 C" p/ ?# M6 s4 ]8 Q
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
1 R& X, \, M/ I6 O* h    scanf("%d",&q);. B* }; N6 t, v1 Z6 ~5 h% @
   p=num;% A  F3 K) G8 P) Z7 F2 k
  for(i=0;i<n;i++)5 K+ L, r8 {$ W6 u; {
    *(p+i)=i+1;# z- C  w1 k' R/ T: ^% {2 }/ u
   i=0;
9 @  ^: v$ Q- Y: z) b7 P' V" J: }   k=0;
7 [. X: U0 Y  A+ u  e- F   m=0;
2 n- B- b( S3 N/ W( a( E4 z  while(m<n-1)! a; ]6 i1 b0 Q9 M, L5 s- h
   {if(*(p+i)!=0) k++;% H, k( p9 F  w# g: M' S! m
     if(k==q)8 e0 S# @. E& D4 G5 _
      { *(p+i)=0;
- c' ~) b, a8 C8 o0 S1 }+ Q( U        k=0;
! F2 O, a9 Q% L4 _! D7 d        m++;
6 N+ i, s7 T% r# T! q5 k7 H2 @3 U      }
" E, @0 l/ w; f    i++;
2 k* n; q" K: \+ D" m    if(i==n)i=0;7 V4 b2 O  W& t0 ?6 y; B- l
   }
! b2 K" @) `. R4 r( }* X0 W* `  while(*p==0)p++;
) {* X+ w9 N7 z; D9 X, \" T8 A    printf("The last one is NO:%d\n",*p);
9 O9 V- y* O2 S- R3 m     getch();1 b8 r5 r$ q2 ~' U1 g$ Y) E* g- c# Z- T

: [0 w+ ~& X/ C5 I7 u, [}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;: S5 f5 q) E+ Q5 L; K2 F& m6 ^
namespace 又费马达又费电4 i+ _, M- Z5 a  ^5 E, S
{2 j. z) ~& p4 z% s0 s/ W  |* [. E5 @
    class Program
5 n' R0 Y4 }1 u5 V- W( P) N! v    {
9 W4 a4 v1 w0 X        static void Main(string[] args)+ |2 I* A* P0 }; b
        {
. {% h! A" c/ t: z, l' ^            int m, n;# Y0 j+ q+ [8 z5 r) k/ S
            Console.WriteLine("请输入数组长度");
: c* E1 s9 ?4 w! F- K            m = int.Parse(Console.ReadLine());//m为数组的大小
7 G3 o6 ]* f* y. q+ L5 v            Console.WriteLine("请输入要截取数字的大小");
: Y* H: f8 O0 T9 u            n = int.Parse(Console.ReadLine());/ {1 ?5 E! \$ b' l+ v2 \
            int [] numw=new int- K1 m9 F! l+ a! a' p

5 n7 n9 ?$ w! G+ s/ p: y" i  s- w&shy;&shy;&shy;;
- a% y" m9 B! M2 C/ ?            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
6 L5 _$ R; v, g1 l! |3 z) A4 g            {/ `% s' f! P# g3 U- x
                numw[j - 1] = j;  E! R& Y9 n8 K: w+ v. v; t
            }
4 H6 ?( O7 p8 l4 _0 v5 z* t            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!1 j0 T8 [+ J; g. E0 Y& k  S, t0 O
            while (d != m - 1)
/ [/ S2 Z5 J% n- Z- N' C8 \. _            {7 ^1 |1 U, K& g
                if (i == m && d != m - 1)
% Z. H! D- U2 S8 V1 T- o# \0 w# y( [1 _                {2 u: r6 N# `2 \6 d/ S- t
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!5 y  T* L$ Q1 N$ N
                    continue;
' i2 f  v) V0 w3 B* y% s4 G                }
2 M, [' o0 P2 _( J% z                else9 e, J: c+ J  r
                {
: S( X: n% k/ W                    if (numw[i] != 0)
0 o( f7 Q6 m2 a" L5 m* C* F$ c. U                    {
# x) ]; o6 P) f, y; ?( V% r3 V                        i++;
+ M7 l2 j' l7 S                        k++;
/ a3 k; v% p4 U, w- R: Y9 @( j                        if (k == n)
2 Q1 z( I& t9 D8 T! |% d0 z/ n                        {, k1 ]' @: N5 U: B* U  E
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了" X/ `; n) H" ^/ B! b; [
                            k = 0;' ~: ]# k4 i8 g! V
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小10 K: J1 L/ _1 A) h
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 R9 a5 D: f+ s" T
                        }) ]& y1 [7 i; i% L: ?
                        else//输出暂时还没有改变数组元素的值
# e' ^# x* c+ ?- u* I9 d0 J                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);% L0 F/ Z+ n$ \5 ^: h! x
                    }
" q/ d5 @, m5 |9 }# V+ h) y                    else; p% [8 z/ f; N) g
                        i++;//数组元素为0,直接跳过,不计数。。。0 T$ c2 Z3 _* e6 U
                }1 t& b5 i9 U- }: [1 P. `/ }" W

+ ?5 s9 v* e0 F* N& {9 Y
& _: H; M4 c. z6 e# j' h; y( k            }//结束while循环8 Z$ W9 \# g& d. L
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
3 S2 p/ u1 R0 n           # D# c: ]2 ]: G) T
                if (numw[i] != 0)
9 W. s# O$ h9 Y( s                    Console.WriteLine(numw[i]);% Y, F, L! B) N9 f; A5 O" ^  a
           
$ E% {3 A$ R7 z( }# d- ]' N# y6 y            Console.ReadLine();
8 b, E* Y8 p; B- `4 P4 V5 t/ U) L        }: z8 i1 l  z, R  o6 D4 I
    }
; o) r  U  o1 o! @7 c) Z( M}! T0 V# o2 E+ _3 O! O
小甲鱼最新课程 -> 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-4-23 04:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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