鱼C论坛

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

猴子问题

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

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

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

x
大家好!
$ E" {1 o( @& y$ H这几天我在忙着编一个问题,我用了一种方法编出来!- U8 i* X) L6 v& o
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!5 e' T: f+ I+ @/ U3 a
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 + O2 g0 w& V6 ^0 y$ y  }

5 @$ E1 s$ J8 V2 D! O3 X5 a3 V: T$ p( Z7 t' v/ C( O
                            题目
6 j1 S2 s4 [& m4 W8 E4 M/ |山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
7 r" A  n2 B9 q5 K# `" y第一种方法:利用循环链表9 }2 _9 F4 u" {
#include<stdio.h>  Z" t% E( r  U1 f+ s- c" T1 S# a
#include<malloc.h>8 B# ~+ V0 w  B
#define M 8            //共有8只猴子
9 W1 B: \4 n2 U/ O1 Y#define N 3            //数到3只时退出第三只+ @9 y1 @( O' O% u; G
typedef struct monkey. l; S- E% A4 ]; `  r
{int number;
; {9 L1 w0 z1 s, G+ Q1 U# iint flag;5 O+ h& @3 ^; ~& m
struct monkey* next;
) W9 ?4 s+ K$ R! L}MONKEY;% m) u+ {5 s0 j- p/ C5 g+ Y. s/ k
main()& E; v. W9 h" e- B
{ MONKEY *head=NULL,*p,*s;# l, v+ h  K) }0 u  }' S/ Z5 _2 k. i
  int i,sum=0,count=0;
0 ~+ l$ U/ R: P* M# j  clrscr();              //清屏
* s- ]/ E% W8 v- W7 r  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
- [- d  m- a( h  y- {5 M& G4 M  p->number=1;p->flag=1;# K8 Y" a( _1 ^: w. y
  p->next=head;" `/ P8 s3 m, A! ?9 Q) i) L
  head=p;
5 ]3 r8 Q+ c  O! g  for(i=2;i<=M;i++)
- L4 s. i* u; m1 R9 E    { s=(MONKEY *)malloc(sizeof(MONKEY));
( U4 q  [/ p+ u4 m     s->number=i;s->flag=1;# e5 T. |/ A7 v+ I! T2 z
     s->next=head;4 U. k" L! F/ T9 |4 o# p/ [4 ~
     p->next=s;p=p->next;0 R' w. I/ t$ A& _% S# q: Y6 i% }
    }' c  S, R! e- d' s! z3 y% p
    p=head;/ N, H* f7 ~9 K( E( C2 h7 [
   for(;;)
7 ?0 v0 @1 L8 w0 b- u) @    {if(p->flag==1)
* N9 {9 n/ p; O8 _) {/ @       count++;
# \1 F) }$ U2 a     if(count==N)1 c4 ^* a' T1 q( O
        {p->flag=0;
. P8 U) E$ Y$ w         count=0;4 N0 G% o) d4 u" B
         sum++;}" p* A2 T' T- k
     if(sum==M-1)
9 F9 |$ ], L1 N2 R) W. t        break;
# R9 i5 r2 {# i- v     p=p->next;
! Z7 P& d. l  H3 }0 Q) g1 p    }
+ H% c6 L5 P+ f. s1 S  g# H* a    p=
5 R4 Y3 M/ x$ v8 ^    head;
. G  A4 [* D# ~, s. c3 L! S# h    for(i=1;i<=M;i++)
% ?; f* z% x, F' M& N    { if(p->flag==1)
4 S. f( f8 _* e# P1 h" _% m        printf("\t%d",p->number);4 p4 N  g6 g/ I; [' P- r4 y
      p=p->next;5 \0 a8 d; R1 p
    }6 c4 T1 O2 I0 J# P. |
6 k% W/ T7 `' E) C  I3 l" s

* ~5 y* j+ k8 T( F
5 T, Q; R/ E9 x! d; u- r}

! H9 ~' s) ?+ d! Y$ k1 o% i第二种方法:数组3 A. s  F; I, G3 I. j% a4 q: r
#include<stdio.h>- G( P& V! p% @8 h7 H
#define M 8
# C0 ?2 v5 G2 n' i7 w6 I; X8 Wstruct monkey
" b+ @* r/ h- ]6 x& [. S4 h( K{int number;
9 ^7 @# @2 Q! ?1 Kint nextp;
- [  e1 L% V' v! g}link[M+1];
8 H! g+ y1 z$ o
+ a, j9 v  G9 o$ N9 W' vvoid main()
$ y! F  U! A' V' N1 D: z{int i,count,h;) p3 H5 s1 v( P1 W0 s
for(i=1;i<=M;i++)
0 C7 k9 e9 _1 [/ L0 D% q{  if(i==M)
7 M- f! y) ]+ p# [  O. Z/ B( J   link[i].nextp=1;
* ]3 e" n7 p; D, P" {6 f   else
2 y- O4 H# Y* r& Z5 k- f; Q" J# Y   link[i].nextp=i+1;; L& f5 T" ^! H8 r$ S" y
  link[i].number=i;: y2 a2 M/ v( e
}9 [* J2 u8 i# v. }. h8 g& I
printf("\n");
  M+ @; v6 l& G8 e% Z, |count=0;
$ ~9 _$ _1 \: H( a( L/ X/ \3 D8 Eh=M;
: ]* s! ^/ e+ J- q7 `. V* wprintf("依次退出的猴子: \n");
, P9 ~- l  x* |9 V% Z, rwhile(count<M-1)
! u2 F. u# j6 {{i=0;1 l- ^' x, p* v3 m
while(i!=3)! c2 E9 g' j& i* q1 J- }9 Q
{ h=link[h].nextp;- N- z) ^" N  E& C) u! i
   if(link[h].number)
! ?6 @  v& V$ k     i++;}( X& D7 T% n; n7 ]

3 m3 j: u  Z% L  S2 w- Y; jprintf("%4d",link[h].number);1 i9 M6 A8 P/ m8 c' q- D) |6 ?
link[h].number=0;5 x, t2 H9 O2 b
count++;
; T9 r* Z' J: ~3 j# L9 R. M}" C- Z; j7 i7 @$ m/ ^3 \/ z
2 l. K4 N" X; Z( m( @9 N( P- w
printf("\n大王是:");
0 l6 {# b4 O( S, P: y, _  for(i=1;i<=M;i++). H3 C3 b0 E4 ?; M
  if(link[i].number)7 u& J! ~; v9 H& i+ A  f* N
    printf("%3d\n",link[i].number);
) ^5 C' D- c1 h2 H0 t# {5 }. {$ e+ F' w( c% S8 A

$ y1 [1 N4 w5 N) R3 W5 B, Y}
% y: R! }7 w( c, U" V7 S
第三种是普通方法for循环

1 A+ T/ Y- d9 ~$ W#include<stdio.h>
' i* W0 m2 z  E" B5 Lvoid main(), e4 j/ X4 c( p
{ int i,k,m,n,num[50],q,*p;2 H7 L$ u: I+ Q6 _5 a' v
    clrscr();
2 Q* I- ]% Z) R. \. q1 I   printf("input number of person: n=");
0 ?! N; ^) U% {. i3 \    scanf("%d",&n);
! U2 J/ U2 b9 }4 d2 l3 nprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
0 q5 v5 x4 f& m# S: r: ]. _# `    scanf("%d",&q);
! v; S$ O  |5 B( I7 J, T3 _1 h   p=num;
- C, C4 B3 V, D6 I' F3 X% g  for(i=0;i<n;i++)+ R0 @* w( A- @! q0 e
    *(p+i)=i+1;
- c8 _# d' A. r3 x9 R- M   i=0;# ?" f0 z7 H) v, |+ `
   k=0;6 [3 E- B  f+ f& X: s
   m=0;3 v. n$ n: a" d- `& o; ~5 G
  while(m<n-1)3 t$ x: [3 F' L6 i
   {if(*(p+i)!=0) k++;' T! j+ G& c4 k3 \* g. O5 L/ i) b! U
     if(k==q)
/ i0 l2 n4 E" ~$ e! H# ^      { *(p+i)=0;
5 F! T  f" W! x6 a        k=0;: W1 m$ E0 j1 N6 Z$ N
        m++;
# u9 L! h' Y; b      }/ G, g" ?4 g8 x1 T* ^6 |  k
    i++;9 ^+ L/ F2 O% y3 H
    if(i==n)i=0;' p* k6 o2 h" h& n
   }
, ^4 X7 g, h) P" f) b1 k' F  while(*p==0)p++;
9 q! I! a/ E" s7 W  B% f    printf("The last one is NO:%d\n",*p);
+ z% C# ]7 ^6 w5 l$ {% I     getch();+ p+ S% Z5 k4 O
& z8 l$ f4 |0 \# M* Y1 o. d0 g. h# U
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
, {$ M, ?3 O/ K/ A: \2 C* Vnamespace 又费马达又费电0 j) e1 P- A% {/ z( j8 Y. }
{
( O5 n' n% z: m- e6 S, {8 L    class Program* [- ?% M. a, n+ E1 T2 P+ |
    {
( j- S5 J7 H6 U8 b        static void Main(string[] args)) t4 ~) L3 v* [2 d9 Q
        {1 ^! B1 P7 x! x
            int m, n;
2 M, }; M+ q3 `) _8 o$ c/ b            Console.WriteLine("请输入数组长度");
0 o( l4 r2 }! f% J3 n            m = int.Parse(Console.ReadLine());//m为数组的大小
: }4 m9 S" N& f7 @2 k' J            Console.WriteLine("请输入要截取数字的大小");
$ A. O3 t6 C% E; c8 c/ {            n = int.Parse(Console.ReadLine());
, p" Q6 v. l2 J% {6 e8 l" D            int [] numw=new int' D; x# k; _( j( C. y) l4 b& k2 b- x

, ?5 n) n2 Y  ~) J+ k&shy;&shy;&shy;;
3 G  x( u# v( h+ r& ?9 c& N            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数  W8 F. a, x3 x$ x/ K' f
            {& b* r; D/ w' M; K  D
                numw[j - 1] = j;
( I/ t% Y; o4 q1 @, q            }! s+ I5 ~& `, @/ C* `4 V" x  L
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!/ q' H: G4 \% i
            while (d != m - 1)
4 f7 o$ G7 u$ A+ O3 I            {. M+ u" D# F$ y' T; I
                if (i == m && d != m - 1)
7 L2 C0 |' B) X8 |                {
; q4 Y) l- U' S; a( p                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!4 N, I4 g* t* g# i) ]
                    continue;% V6 V% M) L4 T! s
                }  V1 B; E* e4 p  _. i& e% G# U% t  S
                else; e  [8 k6 _9 i% ]2 b& s: M
                {3 o1 t) o8 o" B& G- V. U5 }* g
                    if (numw[i] != 0)
6 i$ S2 m# [. a, [2 G) e                    {
* x4 U* J- w) Y! Z1 [5 {                        i++;* k2 K3 w  m; w5 Q
                        k++;
1 r+ p; _  |8 T                        if (k == n)
5 |. P9 p" h0 q" T4 Z# l                        {
/ q) f$ u1 O7 ^                            numw[i - 1] = 0;//把在n位置数组元素的值改变了: t2 k% q9 z: u; d' G1 s
                            k = 0;% y5 g7 p1 b3 b+ q2 [  s$ m
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 p+ f% `# c3 i9 i2 P+ W5 h0 o                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);5 g# T# y1 R% X: F* N) U: ^. \& L8 V0 ]
                        }
3 @6 v3 ?2 E+ e- ^- v                        else//输出暂时还没有改变数组元素的值
. y/ \/ X8 C6 ~+ }. O5 y                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);/ z' X& [% j/ t$ Y/ N) R
                    }
- {4 o3 Y3 o- B" t; a                    else
8 i, f$ W# t0 B3 c                        i++;//数组元素为0,直接跳过,不计数。。。
; r8 O9 x1 j# p+ g. @$ k' M5 F8 t                }
. N/ s/ n7 y% a
8 c+ }- f. B" ]. `( k3 H7 D, M; G& A3 g3 f
            }//结束while循环
- P2 I* j; ~6 L  i8 L            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
0 P) q. H& `& q7 G& f# M           
0 g$ V- m3 v% y                if (numw[i] != 0)* u6 R* c- ?9 G; y: W  E
                    Console.WriteLine(numw[i]);( m  {) ^+ v) M  z6 C: P+ e" T4 h
           
0 I4 i, A5 J8 V7 b4 {& `* C6 D1 [            Console.ReadLine();# \( K3 }; D) ?- |/ K
        }
8 ^+ K  Z4 `: K: ~    }4 T+ x. X5 Y/ l) r
}
- h) ]  I7 e; E) ]& I# h
小甲鱼最新课程 -> 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 10:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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