鱼C论坛

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

猴子问题

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

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

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

x
大家好!# b5 G; E/ g5 w4 }$ l; ~1 K
这几天我在忙着编一个问题,我用了一种方法编出来!
4 o. y6 z- ~% m1 Z. |但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!0 q3 W# d& h" f/ A  F
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
) k7 Z/ J2 G3 Q; X' C5 T6 A0 b# C# J/ U

- g* R% b3 e/ L/ h
                            题目  B5 [- I( u- j' |6 `3 ?5 t+ o
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
- P  u3 m) s& G  b第一种方法:利用循环链表$ q* `5 ]7 A( {
#include<stdio.h>" U2 C9 W& U; r' w! E, h$ h9 Z
#include<malloc.h>
5 a$ l& E% l4 L8 h) S2 ?' l#define M 8            //共有8只猴子( r" `7 M; G' ]: C2 [% O9 T- ?
#define N 3            //数到3只时退出第三只( u- J8 F/ r) [4 X0 F. o: q/ ~! U
typedef struct monkey
* g4 Y  z( P4 {; f0 F! O1 y) j{int number;
2 i* g1 n5 a) N. i- wint flag;
$ t; z# c0 w" u8 G. }struct monkey* next;
+ o0 @- D8 S1 h% a( c}MONKEY;
9 X7 d  m+ b6 u4 ?5 d  Emain()+ D4 Y( B7 m; I0 L; {. E1 D6 Q
{ MONKEY *head=NULL,*p,*s;+ \$ C# D) ~# P+ S3 d; @
  int i,sum=0,count=0;3 ^* _5 o, J  r5 Y' B, `" u, f
  clrscr();              //清屏% S- P9 p3 Y: g$ x# I5 ?
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存- N: m' ~4 J- y7 _  n
  p->number=1;p->flag=1;
- j" b* w- x6 A9 q  p->next=head;& t# R+ j" C6 @" @% M+ G2 f
  head=p;
, @1 p5 A" q5 G2 X+ z  for(i=2;i<=M;i++)- L4 U2 |9 V$ o7 c
    { s=(MONKEY *)malloc(sizeof(MONKEY));
7 [0 ~2 R7 i/ W* f7 b+ M! ]     s->number=i;s->flag=1;
! ^" J7 ~6 @, |3 s! ~8 E8 R     s->next=head;' J# }$ ]/ r* v# Q8 Y
     p->next=s;p=p->next;2 }0 P0 S5 F- d9 A- U
    }
# s. q6 F4 A. H* b( @4 ]    p=head;
, V5 Z- Z) i5 W& D% ^* M- Q   for(;;)
  X4 x; r6 Z+ ]* J$ u, o    {if(p->flag==1)7 b# S2 z3 X* Q% K
       count++;
1 y+ g; f6 S9 H8 S9 K1 Z' X$ Q     if(count==N)% l- l- C  z: Y8 e( v5 X7 Z
        {p->flag=0;
, x2 g, K5 z9 @6 v5 {- z         count=0;2 W$ W, d+ i1 \( t" G
         sum++;}2 U4 ~/ W2 i% u, S
     if(sum==M-1)  j5 @0 j" s  i
        break;
  w$ O" j; D9 g6 o- d     p=p->next;
4 X+ H# Z3 Z# u; Y6 g0 K% c; p7 E3 p4 I    }; m$ B0 _% O6 J& a  B/ a) g
    p=
7 Y3 Z0 u8 e+ f. U, Z) |    head;/ l4 H0 i6 M: E) b, V  a
    for(i=1;i<=M;i++)
; P8 ^; X" ^, q    { if(p->flag==1)* [+ m4 `0 n# k8 X  ?8 o
        printf("\t%d",p->number);
( M' W5 h3 c2 l/ q6 |7 n3 o+ }      p=p->next;
6 U8 U# r+ ?& W! c! @5 v5 e    }
7 E  |1 t* d2 P% x. s! \3 y7 J  a0 S8 s% ]) W* i3 r) y
- ~6 v  L$ I+ W# ^' X% P# B/ o( e
3 z  q  ~% {3 @/ L& y
}

' y) O1 W$ w5 O/ N* B8 T第二种方法:数组+ j. t0 j3 V. K
#include<stdio.h>% @( h2 F. _) C# `2 x/ U
#define M 8# m1 r! i  I% J' g* C
struct monkey5 J, X+ \  w* N5 I' S! [
{int number;
- i/ d6 A( ^. ?int nextp;% Y# V7 W7 `, ~5 z  ]  x1 o$ \
}link[M+1];, V) I6 v& b8 y! F  ^% a+ B
, [* m( w0 ?# T6 l" `6 s5 N
void main()" C6 B8 r" \; u# I
{int i,count,h;7 F3 i$ f3 T- b1 `
for(i=1;i<=M;i++)
* L7 O: S. F$ a* a- R{  if(i==M)
/ }8 [* R" {9 H4 D0 D% `( v   link[i].nextp=1;! e5 f( L6 \% b7 a. z
   else
" t7 {5 p5 e8 Q* l   link[i].nextp=i+1;0 K' x% t3 N: G" S8 c
  link[i].number=i;
; e, B! a4 J; b( h$ p' P}( b! f4 t8 T' l5 m/ Z$ N' G' P
printf("\n");
% ^: W" t- l. K8 f/ m  Q+ Scount=0;
  V, ?. z* p7 k7 t6 m" [  Th=M;* ]  X0 j# L1 s9 i. w  ?
printf("依次退出的猴子: \n");, M* s8 O1 ~& Z7 a& ]9 t* _7 R
while(count<M-1)2 r7 m' N* `$ e! Q( \" @
{i=0;% }/ w. I# v4 p1 ~8 J
while(i!=3)
6 D# `, R! \6 |2 X+ z{ h=link[h].nextp;
/ R- m3 Y  B" s0 L( j' K   if(link[h].number)
( y/ m) T8 y6 K+ m# w+ u. o     i++;}8 S: r# l8 B2 Y# I$ ]7 a

/ T. e: H" `5 s* rprintf("%4d",link[h].number);3 _, Q+ d; T( N& P+ ~5 o# O+ F
link[h].number=0;0 F+ m# @& Y: [2 c
count++;
& P, D: V0 G0 G! c' ?1 G}
7 |; ]) {7 T8 L) I
3 I' v3 X# y7 R; V) t9 ~$ S6 b2 xprintf("\n大王是:");
, G1 ?& Y' b5 Y+ L/ B  for(i=1;i<=M;i++)) w( X4 }8 D# j/ h
  if(link[i].number)1 _( {. f" b" E$ H. M; I
    printf("%3d\n",link[i].number);+ [2 o9 A0 i( U% ^% f
, W8 V  r( ]1 Z) Y+ V) f# J- h3 u
7 u: R: o+ y$ J3 H
}

) b1 L/ C& P! v第三种是普通方法for循环

# j% e! ~/ A) I8 I# F$ y" j) q#include<stdio.h>2 V  o: e1 X8 a* }) a7 U% I/ d1 C2 \
void main()4 N, K) u- S, X/ {% `
{ int i,k,m,n,num[50],q,*p;8 b9 p- j% ^( w0 N* \
    clrscr();
1 r! t, X) U% X( w5 K4 j   printf("input number of person: n=");1 s  X2 p- P' A; T
    scanf("%d",&n);
$ ?7 i/ j/ D' `9 ^, G+ l1 @printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只7 Z2 |$ t3 t* `0 X
    scanf("%d",&q);, ^% A! i1 |  q0 p5 c! R0 w: z
   p=num;# R9 u, ~+ W; A& C6 D) d
  for(i=0;i<n;i++)
4 {3 X  J  J0 q6 Z" {8 Z# b    *(p+i)=i+1;, g( k9 S% X! G1 w$ c( o
   i=0;0 c$ y/ I$ ?( e; @! r
   k=0;
# y& L$ k3 ^" \0 `6 F  R6 U   m=0;- o- U, F1 i* t3 t% i
  while(m<n-1)
8 Z, k7 |  D# `, K/ V' k   {if(*(p+i)!=0) k++;. X1 J) B4 x9 Q6 B% v( R) n4 q5 T$ h
     if(k==q)3 t( a! T# Q6 w  u- W! T9 r
      { *(p+i)=0;2 x7 u0 F/ m7 h* n
        k=0;6 W  \7 \: _% a$ O2 [
        m++;; A/ M2 x7 ?. v
      }
- ]' ]3 _# M% \' `  H. D    i++;. K" D( k) }. T4 ?
    if(i==n)i=0;+ i( T. ^! D6 F/ ~2 c$ f1 v& P
   }
5 w  ^$ _. T3 @3 c2 |  v  while(*p==0)p++;
/ T9 \& K, t4 Y7 q6 m    printf("The last one is NO:%d\n",*p);$ ~) l, R# A, b' W: K' c8 J
     getch();3 a# a! R. Y- t# M' {) t
. Y6 r! a( p' \. e. I! E# u
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
2 ~, @9 v) @( _, U6 d0 S* W0 Y1 w2 unamespace 又费马达又费电) I4 [, Q9 R2 u4 C% E
{
/ `! \* D& o3 U# y! y, @6 n9 l    class Program9 z2 z# g$ V. F) E: B& r7 `  s
    {# y- s( T6 _1 |7 f/ s8 j2 H
        static void Main(string[] args)+ m9 ?9 a: q9 f+ {' |; c2 e9 E
        {
( }" m, G" a  h$ B: O  ], v            int m, n;
) P' E% U; _" I' T6 V$ r            Console.WriteLine("请输入数组长度");' d+ e. H9 w9 k' h' j
            m = int.Parse(Console.ReadLine());//m为数组的大小
3 G9 \% q; A# O& c! ?            Console.WriteLine("请输入要截取数字的大小");
  E2 s" }* |: r9 R3 \            n = int.Parse(Console.ReadLine());6 P& h3 N* m* \/ Y* S+ @
            int [] numw=new int$ Y% N4 \, D2 f, \  ]1 x5 ^, `* ?

$ {9 S$ b/ R) o( n' O% ]&shy;&shy;&shy;;6 X$ {: {/ }+ k3 l' c9 j) Q
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
$ L- d0 C8 [* }            {. l% U5 j+ G- |! z
                numw[j - 1] = j;
& f4 v9 O  c. V5 c4 Z$ V) w! h            }
0 C* z* i& f% M6 X( M. k            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
8 M, L8 _, |1 I% u            while (d != m - 1)
* `; G4 A: [# [1 v            {
+ H; O. a) G3 T6 B9 ~0 v" r                if (i == m && d != m - 1)
. m* a" w0 C# T7 l' {  B4 a                {
' x- V# y: {! v/ I$ x4 Y0 j                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
& g2 y5 U8 T) Q: e* g, N8 [                    continue;
8 X$ e' }8 v& [                }
2 H) y9 b- E/ M9 o; |' j; L                else
! U$ @" I6 B. ^2 J1 t0 O$ i                {- ]) K6 f9 Y3 z  a5 b1 r
                    if (numw[i] != 0)8 r. ?! ~& n3 }
                    {
& i2 H% Q7 T  A) \, L+ Q& f/ z                        i++;. h. c, s, m3 Z
                        k++;+ V2 l" Q& X3 y3 \2 u1 h
                        if (k == n)) j, H# K2 `. O1 u
                        {' Y7 a7 H7 W, r* b& ?& l/ X! Q
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了0 `% E7 q* P0 }2 V+ T4 J
                            k = 0;
( J: Y" k6 I" x' A9 g              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小18 a/ c" o4 k! `/ c5 Z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 R! T( _. i- x# A3 t* q$ `$ B
                        }
& T; y7 ?( B; {                        else//输出暂时还没有改变数组元素的值
2 Q( B* @" q5 _" a                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: x1 l, |' z9 K6 y1 C
                    }) T! f: p! P& @+ @
                    else& s, T, ?3 c! I6 y
                        i++;//数组元素为0,直接跳过,不计数。。。; r9 ?8 W5 c& D: w; Y; q9 H
                }
: F0 N  J' k. ]$ w% I7 R . H3 }9 u3 ^0 r' n$ _2 g4 W; @

6 d) B$ p2 y5 ^4 r' z            }//结束while循环0 |. r0 N4 M7 u7 N
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦8 g" k  J8 S+ N$ ^0 G# m9 h
           
6 r/ d1 A' D6 d4 U, x$ ^                if (numw[i] != 0)4 y5 [1 z7 g4 K$ z9 o7 X5 P
                    Console.WriteLine(numw[i]);
& @1 J% d& n/ v  ], F2 l6 t           0 B' S: S! b" s3 U+ `& r0 a2 j
            Console.ReadLine();
+ J' M# A7 w) q1 x, b        }) R/ W6 p: n. |/ B+ B
    }
' Q5 F0 F% `. r& `2 R# @1 f0 t}
* ~3 `( h$ s& R/ a( 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-6-5 18:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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