鱼C论坛

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

猴子问题

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

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

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

x
大家好!
% c$ M# ^& P  R4 h% E这几天我在忙着编一个问题,我用了一种方法编出来!
0 Y! O& I- R) J2 `! i0 T但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!) v( ?- M$ x/ r( f+ j  c0 e
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 b' r6 g9 n9 L7 F: `
% i& k4 [/ L; e1 C9 j- Q: L" q1 ^9 z: R' W" M1 f8 c+ D1 P- ?
                            题目
8 X# h& z1 d" x8 e山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
) X, `/ G5 W$ _8 ]! g# q7 K第一种方法:利用循环链表# T9 |( T) a. h' ~. W3 L- X
#include<stdio.h>! B( _- f, H) Y$ V' X
#include<malloc.h>5 d$ `* I; S% v: ~! R4 \
#define M 8            //共有8只猴子9 n+ g" W& o6 M, ^, S1 l" Q
#define N 3            //数到3只时退出第三只6 T3 S, E$ k0 \4 a0 N; n
typedef struct monkey' N3 t" K: |6 C+ {" e1 j
{int number;
1 x3 Q& I  N; ^) _, R/ K' Wint flag;
/ k' c  ?# E' ostruct monkey* next;
) [$ _* L  w! Q; q}MONKEY;
2 D: x) V  Z0 s" }/ ?% k7 ]& w$ Fmain()7 H7 @5 d; x- s/ Z* O; ]$ L9 c
{ MONKEY *head=NULL,*p,*s;
( Y3 K. j) N1 d; a  int i,sum=0,count=0;& }+ O  q8 v$ p) k  B6 {3 y) j; V, w
  clrscr();              //清屏
! {- \' k; l+ S  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ W6 X* Y0 L+ B; X; }
  p->number=1;p->flag=1;0 R; K8 A. o' `$ z' q
  p->next=head;
1 e& d: O/ U" d0 C2 k  _  head=p;, g& N9 B8 U7 `" w0 V
  for(i=2;i<=M;i++)
$ F( l0 w9 L& p7 T9 k  ~) ~7 B    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 u$ C! I- \  g; P- w     s->number=i;s->flag=1;+ f  w# ~& T% {9 N- t+ R
     s->next=head;, ^0 K6 Z7 N2 c! M
     p->next=s;p=p->next;6 s+ a. \) `+ n- I$ x! q2 `
    }
  i- e9 s, q+ \, ]* O1 Z5 H/ f    p=head;
: [* j2 B6 N: W$ x( F   for(;;)
" g0 M6 f+ N; Q    {if(p->flag==1)# N3 X5 l# p7 g: F4 x0 p# r7 _7 e
       count++;2 b0 f7 W' _. [: r7 g
     if(count==N)" e0 Y# \5 Y7 h" k# @3 Z- F
        {p->flag=0;
0 X& @1 O! U4 e         count=0;& e9 i0 q% P/ i* {$ u, X
         sum++;}
" r4 j! F4 N* Z: _6 A     if(sum==M-1): r6 i5 W' h% t$ U& H; H2 `
        break;# n; ~5 f( ]- p  q
     p=p->next;
3 w$ |8 i6 w) B% E& X  S9 x    }( @6 w% e3 b* l1 ^# L7 f& P7 h
    p=
0 y% F! r" A$ R" x% `2 B    head;- D9 z! I. n7 Z+ y3 j+ ~; o1 G
    for(i=1;i<=M;i++): z# _: J/ K( E0 H  l& F# k
    { if(p->flag==1)7 H/ `$ S4 }6 o$ e; i8 e
        printf("\t%d",p->number);0 Y/ z' R: l1 c
      p=p->next;! a6 K: a. b3 k; R2 r+ u
    }
8 A& E, x0 j9 |$ |6 c' }: F+ s3 ^

$ m4 ]* N  V2 ]+ j' g
, E0 j+ h& G& k% z}
+ ?" X4 t7 _+ t8 M
第二种方法:数组2 ^7 @& }1 d& G
#include<stdio.h>
) C; }( {& k4 j( c4 }9 K$ S#define M 8
6 S  F- o  t0 g$ G: N# ystruct monkey
8 \6 G/ n7 L) Q5 m{int number;( ], n% ^! N, O, O* k& g* H
int nextp;
* w5 W. h- |9 X( n* Y* q}link[M+1];
9 m: C' h- C: F1 ~# y6 r
/ g) J) L# ?. w* z5 _+ I) Zvoid main()+ q1 C2 i+ j% ~7 R
{int i,count,h;% Z5 |; R1 k+ Z! b
for(i=1;i<=M;i++)
* k. R8 f0 |7 b; z: x4 b2 v{  if(i==M)$ |8 t* T4 {0 Q/ t( Q
   link[i].nextp=1;
7 Y, ]$ K  O8 E; ?  Y   else9 B* O/ z! i1 ]. l6 ?- t( p
   link[i].nextp=i+1;' M- [  N& Z" G! h2 i
  link[i].number=i;: @4 ?6 U* n4 W( h
}
& [" e( c. P& S7 ^+ m9 ^# Tprintf("\n");; @( |% m' ^, G, N& m
count=0;
+ p+ _, ?8 d6 E) ~* H& Q+ ~- [& Bh=M;" S2 ~! |: I. Y. q
printf("依次退出的猴子: \n");7 G# b" O5 `: I: R! `. ]
while(count<M-1). v/ z7 m/ N2 [1 Y' D2 O
{i=0;- m8 {4 c; Z0 {4 `9 C8 ?5 \/ `
while(i!=3)% p. l3 i) ?9 S
{ h=link[h].nextp;
- y, Z5 X) E) d( L   if(link[h].number)- W9 {( {0 R! ]
     i++;}* D9 b8 V5 H+ i$ j5 t- r) C( m
0 L0 ~7 Z, c( o9 o% |
printf("%4d",link[h].number);- }) V5 y) ~! a! P/ y. ]
link[h].number=0;
! q! C1 J9 Z) }  X5 F2 fcount++;' ]1 r0 ]! _9 {) q
}
3 T& Q- r0 E4 j, @4 t
$ F* j1 g, j. E6 Lprintf("\n大王是:");
: H# e% X* |( D- ]  for(i=1;i<=M;i++)
% N! o/ r2 B+ O1 a3 s  if(link[i].number)2 B4 L$ v% e! r+ {$ [2 w1 E/ y- T
    printf("%3d\n",link[i].number);
0 i# L9 L5 I  x3 [5 A5 A1 R. T/ V5 D% Z1 P* n! s" P7 o4 r) T
! @3 b1 G! `) d
}

: I0 k0 q+ I) z1 k2 ^# I1 Z第三种是普通方法for循环

# X" s0 ^+ }; N0 B' c#include<stdio.h>
/ M/ f2 n7 @6 l; Rvoid main()% l( O1 q3 o3 v; i' E
{ int i,k,m,n,num[50],q,*p;5 e7 b* {3 @( J' t* d4 M
    clrscr();
" H, T  g) ]7 y; {. L3 _   printf("input number of person: n=");& m4 u* i) I( U3 _7 S/ c7 m
    scanf("%d",&n);
; Q( r& Q$ d0 U( {  tprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
$ ?5 H0 ~3 ?1 z: m) X    scanf("%d",&q);
% G- |& @; E. d* d$ y3 h   p=num;
- c0 \, w* S' W  for(i=0;i<n;i++)
9 I# y& F0 ^  k0 K5 X; u    *(p+i)=i+1;
2 L9 z) ^8 s( p! B. l5 R   i=0;9 n( O8 Q6 y8 Q+ L7 ?# [# D
   k=0;
1 J( |# E3 o' f% [   m=0;1 G3 I# R. _. p% M
  while(m<n-1)
  y4 V* v! [: x% U; s3 E) }7 X   {if(*(p+i)!=0) k++;
! P) h1 c2 V9 c' F     if(k==q)% K: }  Y6 u1 {4 {; K0 B' S! x) k
      { *(p+i)=0;1 g1 b' S+ X- B; q/ c) ?
        k=0;
8 K2 o& J4 t! M5 U$ L- ~        m++;
2 i  U1 @. Y) \* p7 l      }
' k6 ?( O6 D1 |+ H$ v+ v- P7 m. g    i++;, w7 O/ Z1 X1 [( d+ V; w) S
    if(i==n)i=0;
$ S; ]7 Q8 T5 C2 n# K$ c8 o   }. D( O5 t6 V* ?5 u5 U
  while(*p==0)p++;% H# W4 l8 M& P7 s- i6 u$ [, F
    printf("The last one is NO:%d\n",*p);
- r* T3 H) P: I7 y8 I     getch();
, G9 z4 j) a4 j; r* f7 Q2 @4 }3 G% p
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
$ K. P: m  F" |5 W/ Y: m4 h3 Xnamespace 又费马达又费电
3 L0 O5 O- n- m( M7 i/ I; x5 e{
. a# P! A, c* f( H, U    class Program
- q/ X. t, ]- k* \    {
) _* A* w0 G0 K        static void Main(string[] args)# {) b: ~, N$ t3 i: Y6 D* T& t( E& O; A
        {- D0 ^: V9 y& B
            int m, n;  d" A7 n! S+ U! E( x+ m0 k
            Console.WriteLine("请输入数组长度");
$ p( ?; C5 G# k0 ?& J            m = int.Parse(Console.ReadLine());//m为数组的大小6 C+ e: Z7 p/ G2 X
            Console.WriteLine("请输入要截取数字的大小");  V& c4 T2 ]) \% z
            n = int.Parse(Console.ReadLine());# @# h# H- L! n8 C2 T
            int [] numw=new int0 R0 X: C& j( O: N* G5 B2 Y+ Y, ^
, X  j! A! W( T
&shy;&shy;&shy;;& B5 H* |5 L4 s
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数& o/ L3 f* u2 g5 H/ {( y1 n  j( S
            {9 P+ H, I& l5 ~$ g2 u
                numw[j - 1] = j;8 C3 {9 q4 W! t7 t7 P* I1 y
            }
" Z' U8 \/ l8 ^) A+ S! B$ \1 [            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!9 G( c1 s2 k9 ~+ S2 q2 O" ^( E! w  X
            while (d != m - 1)' ~9 o7 N8 e9 W  c& V5 `1 Q" T
            {9 R2 a# G; X+ I" K
                if (i == m && d != m - 1)$ D+ y$ U/ K# N1 ], M. A; m
                {
4 H# h, C( }# c/ h/ E                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% ^2 `4 N) ]% s3 |' ^$ y  R                    continue;7 M% d9 k( J% p5 o$ [
                }4 [* O( r. H* ]
                else- q7 U% b4 }5 e) E( k
                {5 g7 R, {3 A0 [$ Z& m+ j: m
                    if (numw[i] != 0)
6 g6 C; e. M9 U' `% |7 K                    {
6 e/ u* s. q% r                        i++;
+ E" F' i7 |" I% Y: p                        k++;
% M7 y* ]8 h* N0 \                        if (k == n)
& i; J; E9 u* |0 ~                        {- P. r- Y6 P2 D, e7 K1 B8 h
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了" z; \0 W- P) Q; `) i
                            k = 0;
9 I* g! h  f5 }0 T' N              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小17 J% L5 U. W& u7 ~& Y* L! e
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* l( l. R& q9 ^' w$ K& k
                        }
( G) x: q* w, o- c                        else//输出暂时还没有改变数组元素的值5 S1 b0 |+ S2 M- |/ e$ V3 O6 `
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* X& y, H2 q; Q+ y5 M  s
                    }& M* K2 J$ k5 |6 P) G
                    else
' r+ Y4 {, D/ L! A: X                        i++;//数组元素为0,直接跳过,不计数。。。/ t8 ~6 u1 n2 S4 l' ?( X$ i0 R
                }# `9 M5 p- Q6 H" Q3 v: u# ~! N4 D

0 H5 A/ D; ?0 o" @( X6 P/ h; D3 u3 c) M2 S2 \5 ]5 A
            }//结束while循环/ O1 J8 K$ G% Z4 g" d9 P/ [
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦/ F. z6 n" \# `2 g0 B' Z6 k# E
           
7 l" Z2 e. f6 K% ?- a                if (numw[i] != 0)! L+ ^& s3 F( ]; y4 N0 I! ^
                    Console.WriteLine(numw[i]);' U- p3 |% S9 [; M# Y9 \
           
8 G* Q' f- l" }8 |5 ~            Console.ReadLine();
: |0 \+ K; w0 Q/ x/ K9 S- b        }$ D! d7 f8 {. {* r" H0 ]
    }
  x* `+ L5 U. F* \& q2 ?}% y& h! m+ o' P# @0 s. I
小甲鱼最新课程 -> 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, 2025-11-13 18:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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