鱼C论坛

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

猴子问题

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

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

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

x
大家好!
; z$ k+ e3 W0 m$ }0 F) S这几天我在忙着编一个问题,我用了一种方法编出来!
& ^9 o; E- A$ X& e但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
$ k' v& Q9 v9 ?$ Z+ Y- _  S注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
4 y6 [7 ?) a! r4 Y' H) v2 |$ j1 j% x3 b' w
% U6 S2 ?" Q6 N
                            题目" P6 }& u0 `8 y, I- B, A5 a" ^
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。: N2 V6 [8 D! k
第一种方法:利用循环链表
& V& @+ O7 m. x* p#include<stdio.h>: Z9 h, J& [& H5 @
#include<malloc.h>( X/ p4 ?4 O* P, [/ q
#define M 8            //共有8只猴子
5 u  M) p3 E9 h- k#define N 3            //数到3只时退出第三只+ r# D3 n! }7 X3 |% A
typedef struct monkey
2 _6 Y% F& D! n+ Q0 f% [2 _{int number;5 W4 I( @9 k" K1 ]
int flag;
2 W; a' P- i) R, U' ustruct monkey* next;1 @# R* i$ S) Z; ?" R
}MONKEY;2 d. v& F4 O9 V+ L" W9 ]. P# [! u
main()
% T* B" H$ P0 @; ^+ X{ MONKEY *head=NULL,*p,*s;; Y2 D5 j6 M9 F( J
  int i,sum=0,count=0;
9 y: M1 s- E: S  clrscr();              //清屏0 N( G& `" T/ H2 q
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存- B, L$ c$ F" D7 H! o5 R
  p->number=1;p->flag=1;& }; q& g) ~; f
  p->next=head;
. [' Z( @, G  J, i$ M  head=p;8 r; V! I! W( L: _3 z
  for(i=2;i<=M;i++)
  M, t: J4 M2 N8 d    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 N( o$ `) v( X  q3 H( E. p; K     s->number=i;s->flag=1;
$ ]& R+ I8 D$ W& ?$ \: C     s->next=head;) U7 c) B/ T; y, K+ S7 w+ E
     p->next=s;p=p->next;2 H7 ]: }" @+ G
    }
* }- R2 O1 i) n) ?  ~    p=head;5 L3 B0 L1 z2 o
   for(;;)/ }  J1 f5 J2 n
    {if(p->flag==1)! S$ ]. @% }- N* ]7 G1 N7 X
       count++;
( _9 e0 y1 w; p7 _  ^; J0 V     if(count==N)
3 o% ]( b) R: W/ Z! u7 F        {p->flag=0;
5 M4 P6 }+ X# z# c         count=0;6 }' m2 `& C* u$ f
         sum++;}. J0 s; O2 k  |
     if(sum==M-1)
/ W' l  E, F' @        break;" i3 a. @% Q* T% y& A$ U1 }
     p=p->next;% `' u+ `1 y8 x, S, w
    }
4 V/ z# f1 `' ]+ H6 B2 h, T9 k    p=
& n1 w9 u* [% n' F0 ~' u    head;
% N' o0 m. [$ ^! F! q/ E% M* H5 m6 a    for(i=1;i<=M;i++)
# M# \3 x1 M5 h) S0 ~& Q    { if(p->flag==1)
" U4 a8 X2 a, c5 s' A' }        printf("\t%d",p->number);1 \; p' B8 F( n. [. l
      p=p->next;6 O8 e& w% j$ W7 v$ s! y
    }
5 L- X, s) _+ c5 x5 ?/ o3 U2 Y. q/ B# x
1 K2 G; I6 E5 L. B+ _" @+ ^

/ r2 [0 ^' A; l. r& c, }" d. H}
$ g% ]' W3 e9 `$ r/ W
第二种方法:数组
7 M4 l" {/ D" S9 x0 V0 ^. s#include<stdio.h>) b1 x! j. M$ F. [& Z& }
#define M 8
+ M# W% t% i: S) r* d9 A- ]struct monkey0 T5 J. \! ?. {/ Q9 K  O1 k$ s& ]
{int number;; K. E& I- s0 i1 ?
int nextp;& m" y3 W. d2 ]# F4 a
}link[M+1];
4 }: p# n/ n) ]! q! O  ^# [9 H7 A7 S+ q3 v3 S% {  T
void main()8 p8 Q' v/ T( @1 c" I7 O
{int i,count,h;) H- l( U6 j5 u1 y
for(i=1;i<=M;i++)/ @  ^) g" k$ M
{  if(i==M)
$ o+ Z% f4 I7 u   link[i].nextp=1;" T" h1 p$ h1 U6 h+ e) [
   else
' z8 W9 r" ~) i' s; @0 c9 M   link[i].nextp=i+1;
# H+ [. w# X" s  link[i].number=i;/ s# B! D: X, r9 @# o7 h  M0 ]% U
}
/ M7 {. X/ W0 T( X5 W5 R/ n+ j- Sprintf("\n");! i' s3 d' ~7 ]8 x
count=0;
# l/ O# r6 N* _/ g1 Ah=M;& ?0 J' i" T) m- @. v
printf("依次退出的猴子: \n");
: S: ~' M9 ^* d* h% c: o: Dwhile(count<M-1)
3 H4 Y3 d0 R) E9 |# a# b{i=0;& p7 R& m' o& W( F% C( S2 s& W0 x: f
while(i!=3)- m* _  E, w0 Y# a# [( j4 y  Z0 g
{ h=link[h].nextp;
& [+ D5 t3 U. D+ Q6 `% K   if(link[h].number)8 Z* C& q) R2 y/ Y7 u
     i++;}' v* [" M' v: F8 X, A

7 P* ]- S. c  ^; n! {- M; |3 i7 T" ?printf("%4d",link[h].number);: p8 p& H$ ]1 q% R
link[h].number=0;
) Y* U1 r" I1 K  P" u5 fcount++;& U, m$ I+ g1 X" E2 y, _
}+ Y( R9 ?* S$ Q4 J# a% Y

: X8 P! o5 L0 X3 `printf("\n大王是:");- ~' i6 u  j% ?' f6 i9 H9 r2 F% d
  for(i=1;i<=M;i++)
1 Y+ p; C, \) `  e/ B! ~2 r  if(link[i].number)
1 X7 v- r) E: p( t4 k    printf("%3d\n",link[i].number);/ F+ R/ G7 g+ f, S! w( b$ k4 |1 A( A
& N% v1 t$ n4 N$ m$ W

0 R) C/ h7 T( O& y; z' M( \}

& P+ K7 n* V! t7 w! u第三种是普通方法for循环
( Z$ \7 o2 {8 F: U/ s/ d
#include<stdio.h>
: N/ J( ~: ]$ x3 k) [; Jvoid main()
. ^) v/ ~9 X3 V& }* n5 K6 p7 Y  [' H{ int i,k,m,n,num[50],q,*p;
, }5 j; I8 c( s  M3 ]) q, a+ r8 ?& D    clrscr();
* x! e% `7 J8 A6 j4 |0 Q, T" D( v   printf("input number of person: n=");
+ n  Q! v4 `3 b$ l6 W1 P! {$ Z; P    scanf("%d",&n);1 C7 _2 S0 t9 i; o0 C; j
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% [7 Q% A& J  r2 ?3 E
    scanf("%d",&q);; S0 _+ b$ Z1 l. ?- O
   p=num;$ j% r+ L* x' r: I6 V" z
  for(i=0;i<n;i++)* {) j/ R& K$ o6 J
    *(p+i)=i+1;
% d( V, v( j, k   i=0;
! E7 l% @# @9 h7 @   k=0;' ~1 Z; J+ K2 e1 E& p+ r, i" ^
   m=0;' O9 _; b1 d1 D( l& l
  while(m<n-1)" S$ ^$ g7 ^" x, B/ D
   {if(*(p+i)!=0) k++;
6 w" @+ p+ F6 `- r9 V% h     if(k==q)
0 L+ U' z2 r0 X0 s# N      { *(p+i)=0;
3 R+ G% n4 v% A  e$ C0 I        k=0;" ]6 T7 D& |# [# j! g
        m++;
7 l# r# @# i1 b      }
: L& Y! `: C; E5 G  e+ j& _" I# r% D    i++;
. ^0 Z8 Y& S5 H! ]    if(i==n)i=0;
$ ]& ]% f! S* x0 B   }
! |! g8 i/ W1 \& n* q  while(*p==0)p++;) X$ c1 R1 N* z* o( W
    printf("The last one is NO:%d\n",*p);
! D; i$ B; F4 g% D4 K9 y     getch();( f- E( }- B9 |1 i+ t6 R

- b* f4 H) u8 s6 Q& ]' o" Q6 w}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;5 U+ v- [; u1 y
namespace 又费马达又费电
! x' k# z0 p7 S; x, n7 b{
. m* L! u7 ~! P5 }  m5 c    class Program, ?; k  D1 X# r: X) U+ v7 q& ]
    {
0 n+ \2 P# O2 P' O# }& a! y        static void Main(string[] args)
( J7 ]! u4 y: J) s. W        {4 c+ b; e7 J1 F  D
            int m, n;# k  w9 |' y7 b' o* J' j
            Console.WriteLine("请输入数组长度");, `% N0 N: F2 r6 o
            m = int.Parse(Console.ReadLine());//m为数组的大小
+ R( G6 p8 p) }. @            Console.WriteLine("请输入要截取数字的大小");
3 Z' f! J: Q; U1 \. b            n = int.Parse(Console.ReadLine());
  u/ b" M8 a% K            int [] numw=new int
4 I+ W; R: {% {: }" f7 ?; G
/ i( j1 z9 U* }+ ^/ G3 R: c/ x&shy;&shy;&shy;;- V  c0 f& y5 r# V1 q7 {. `
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数, Q, O# d: O' S, h' p
            {  N* R2 h9 H+ B' ^7 X+ D
                numw[j - 1] = j;3 L$ L" S4 {7 D* g0 d
            }
6 K/ Y+ W: v4 r            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!4 k$ A3 {' a; g/ J" b
            while (d != m - 1)
% F! I8 ~5 k$ j# ?4 b            {. @7 Y# `) G4 ^  }( F9 [% ~
                if (i == m && d != m - 1)' S' g* s" r& u/ p" ?
                {
# d  [9 t  C$ E9 N# V$ }1 ]' P3 v                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!" ]1 a, O: Z2 h7 _
                    continue;2 \0 d: d! Q. v5 l+ Q, P+ n' K/ z$ R
                }5 k7 r( ^4 r2 `: L
                else4 _. k4 z- X) c9 ?. I
                {
, L9 }' S- @! E9 v3 P+ P( U: q( F1 j                    if (numw[i] != 0)
" C1 ^3 E9 C, Y                    {; [( s3 ?: Z7 O% m
                        i++;1 p# h4 Z: k) p7 ~7 c7 F$ y, ~- P4 k
                        k++;- {/ ~7 c2 e0 w5 g2 E& Q! J/ q! R* ]
                        if (k == n)
! f" h& N5 J# B+ Z                        {+ e9 c$ h( [! N7 ~
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
; g1 O! \% K# V6 x                            k = 0;
' M7 I# T( z  g- U8 J0 a6 ^" R              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# g1 R) v1 S; [8 ?/ E- {" J; q+ C                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( F; n( s+ m. y. i% g9 N/ N                        }5 t& @  b4 _5 N
                        else//输出暂时还没有改变数组元素的值
% I! J. [. m- u6 `6 s3 G                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);4 Q& N( y0 O$ x; l' g0 ]" S% G3 P
                    }
4 W0 z8 [9 j  {  V                    else5 D6 Z; ?! Q% o5 U6 A4 J' b3 F8 }
                        i++;//数组元素为0,直接跳过,不计数。。。
' h: Y" n; t! ^# G& M) Q4 E                }
# V; c# i* A5 M; q 6 g( h* ]% S$ V/ T  V  l
  F7 M, @" O: ^! ?" e$ D. i
            }//结束while循环
( E: h) i3 q& L: b; s            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦! Z  I6 h- Y% ~/ L2 F: e- \6 }
           5 {2 W$ Z% @( c7 ?- y  {) P7 x) R' s
                if (numw[i] != 0)
1 `( m- f8 d5 B" F                    Console.WriteLine(numw[i]);
( N2 k) A9 ]7 K* c; w9 v. v2 y           
3 w( z& u$ U! D, z            Console.ReadLine();* a9 k2 j. y9 Z# i$ f0 S" H! ?
        }* n* U1 B" O( T6 F
    }
; n' L( J+ g/ q0 F# a/ h2 Y( ]}
: T2 X8 D, A1 s: P7 i4 n
小甲鱼最新课程 -> 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-7-27 13:58

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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