鱼C论坛

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

猴子问题

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

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

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

x
大家好!
8 F0 i/ X/ H5 S* A4 C3 o- d1 O+ ~) M这几天我在忙着编一个问题,我用了一种方法编出来!
& |9 V! T' Y; F1 t/ t但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
. Z& Y; \0 L, Q) c3 ^注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
9 j$ L/ i5 c7 @7 X1 S
$ Q% |* ^9 c2 m( C! I8 Z1 J. P. l4 S  z* n+ b( C
                            题目9 n2 I$ Y! X. j- X
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
5 ]  B" R( U' `; N2 j) H" O3 s第一种方法:利用循环链表' r6 x. V1 i4 A  t
#include<stdio.h>7 A8 R6 Q+ O- \/ S
#include<malloc.h>, X1 j0 h, R; L! D
#define M 8            //共有8只猴子
, O1 L! ]1 t3 d# N8 W/ x4 W#define N 3            //数到3只时退出第三只; ]0 [# X8 N" C& `
typedef struct monkey
+ _( ]9 d9 B9 f, i+ r{int number;
0 {1 ^* i/ w7 Z( a! W* Q$ vint flag;8 ^+ I, Z) o3 F- \4 I% ]
struct monkey* next;! h+ R' |' Z- p4 k3 p, m; P2 L3 m3 l) Y
}MONKEY;$ C3 o& j& t* I$ t6 D
main()
1 {; ~% M% d' Z5 e{ MONKEY *head=NULL,*p,*s;
4 c8 ^" C! y% K* _  int i,sum=0,count=0;
: C* m% Z! Q7 L* e8 }. x% m  [  clrscr();              //清屏
4 ?9 O& r* R" k& [4 S; o  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存  L" _/ i$ O$ P
  p->number=1;p->flag=1;
; S$ B# S$ @9 i+ ?7 \+ Z: {  p->next=head;
5 ?2 G) K; h% ]  head=p;
3 a$ H& d* V' V. f& o( y7 L% ]" c9 u  for(i=2;i<=M;i++)" G  W, c% e; t
    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 o' S$ w' Y& k4 Q     s->number=i;s->flag=1;$ j! @8 u8 b$ K1 l
     s->next=head;! R9 W3 |2 B2 r3 J1 X
     p->next=s;p=p->next;
% k3 \& }+ a7 T$ p' f/ P+ B    }0 \) v  q* E% w9 |+ n& d7 T; W& b
    p=head;
& [( n5 R/ \  W6 d0 G- l  k   for(;;)+ H0 K/ L. p( U" U
    {if(p->flag==1)
2 D8 S4 J1 H! J% }* h$ y. B. k4 c       count++;
: B) m. d$ i# t2 L' h, e) U5 @3 d     if(count==N); [" v) ]$ k: N1 a/ P/ _
        {p->flag=0;4 k$ I( t5 J) C- T7 O
         count=0;
0 _. g" C  l" w. J* ^) G         sum++;}
# r" r3 ?* m, g( I5 o     if(sum==M-1)* @( f# V% U+ C8 @6 d
        break;$ ]$ h8 x7 Y  }4 c2 l1 B# q* r8 V# r
     p=p->next;2 K) t2 `/ @2 }6 e" ~
    }
) A! G, p" v. q! e- ~( U    p=
4 c. `# f0 z# @8 S    head;. m4 P* O9 l  H7 a  S, g6 R/ G
    for(i=1;i<=M;i++)
. V5 j4 K% E3 U3 P6 a    { if(p->flag==1)
8 j4 R9 R6 w+ _4 A3 B. c9 U0 i        printf("\t%d",p->number);; L. C) m5 D5 a' e1 s, p) ?
      p=p->next;- g, k) j; p2 R9 H* v* r
    }: Y1 F+ f- l9 B' ~! V
. t! K0 q* Z5 u7 ^8 r* T" |8 ~, P

" Q( W4 w' N( p0 [! H" j8 E0 |9 v0 V, B' Z1 P$ m3 K2 D/ e
}

& S2 o9 ~& q, Q+ E第二种方法:数组
7 }$ @2 @. V: Q#include<stdio.h>5 y' [9 B& c. G5 O3 V8 s: U
#define M 87 }) `1 q* Q. f& g: @& b1 ^
struct monkey
, h4 G' I5 p' Z% _6 N5 `{int number;) S3 R' |: ~. [" t
int nextp;
6 b) i) M; d+ \; w0 w}link[M+1];1 }+ ]- v  B0 H% B

$ v, V6 [5 ~4 Z! q& \void main()
- i& O' }0 _2 N* W& t{int i,count,h;% ?: h. K' c  m
for(i=1;i<=M;i++). |. _3 l3 K, o
{  if(i==M)
  a) V" m( S5 a1 L   link[i].nextp=1;+ D. g5 j4 [8 D- o) x
   else, S7 F7 p5 H/ T/ _. |5 Q, F4 |  j
   link[i].nextp=i+1;
  u  y! `8 E# l/ e  link[i].number=i;
' H' |+ \( W" ]; i: R5 U9 t}
4 l1 g: j* g  ]% J6 T& bprintf("\n");* \# T6 \8 H( j& B' d; a% t
count=0;6 C; {& B7 V; n2 w+ Q& Z3 ]
h=M;
" ]+ l# a. x; v# @$ L0 R5 `printf("依次退出的猴子: \n");1 h0 v1 E9 k! W
while(count<M-1)7 R2 q# ~, ^$ y/ M1 Z5 i
{i=0;
* y+ H6 r: f: ~% d' f6 Bwhile(i!=3)
# v# b, H; g3 Y3 R! h) B/ y{ h=link[h].nextp;( B, S8 D* l' S% f" {
   if(link[h].number)% D" X5 _, ~$ u+ Q- @/ G5 E# e
     i++;}3 }2 o6 f( U; n* K* d6 R

, Y2 i+ X: C9 u7 Vprintf("%4d",link[h].number);3 T/ N' Q* h& L$ W- x$ O3 K
link[h].number=0;5 a- @+ P5 h. v! o  X5 J" \% i
count++;1 c# S$ X+ j2 k3 P9 i( p
}
$ h; f2 C! h  ]) r- _* ?7 J: F! D0 ^  i% E7 M: G
printf("\n大王是:");, k: Z+ G$ l4 T, s# I8 F7 t) ~
  for(i=1;i<=M;i++)
. e* A. W; q' k  A: M; j  if(link[i].number)
" q! K0 c! `* G+ ~7 b, }$ C    printf("%3d\n",link[i].number);; X( c+ t2 K) `+ ^8 y; ?! Z
+ p$ g9 g, V- M' I) I
' [7 a# Q3 E. w. Z- z1 ^
}

# D; K( k+ j6 h% x, `7 d3 u第三种是普通方法for循环

3 R2 F* N; M1 _& ?  Z" b% Y#include<stdio.h>1 j. q1 S+ D( ^/ i, a" b
void main()' d3 |- w8 h- x
{ int i,k,m,n,num[50],q,*p;* n: H0 U; M0 F1 z: h
    clrscr();
9 T. E1 T# f# z   printf("input number of person: n=");; o( H7 e! [* ?7 r5 `# W
    scanf("%d",&n);
3 D: {9 t  N' i$ D1 Q3 D2 R" nprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
* p4 c" T3 V9 a7 U- ~6 x) l" k    scanf("%d",&q);$ |2 ], P2 w/ W: W, l( A4 i  t
   p=num;
$ ~; {+ Y2 U" H- G4 O4 j( H  for(i=0;i<n;i++)) G0 T2 {9 K2 i' f
    *(p+i)=i+1;
) h6 y+ r6 {) \) ~: |   i=0;
: v5 e" H0 k3 T4 d  l   k=0;$ V4 o! m. g! d/ Z
   m=0;) y8 z2 V: X. D8 Q/ y+ S' H& B
  while(m<n-1)
$ D' ~, p1 ^- K& Q( t) Q/ X9 _   {if(*(p+i)!=0) k++;
/ Y; k, B( g& o) @* d     if(k==q)5 j  _. J$ o5 R; Y0 o- Z
      { *(p+i)=0;2 p9 P, f9 X2 d
        k=0;( ~* w7 k' p4 n3 S- g3 H( |
        m++;/ v7 G! K( t& I$ y- \5 e- E
      }8 }7 y  t+ M/ D1 ~- T) t+ Q+ Y. ]& Z' k
    i++;
0 r) y* o0 o3 v- I  x2 s$ b    if(i==n)i=0;
& K- S/ S4 \, `8 |  `   }
& _, i2 L; D/ S: o  while(*p==0)p++;+ t- H' a5 E/ a+ `
    printf("The last one is NO:%d\n",*p);& C$ {0 x- ^- I( S
     getch();
! V9 w/ X* d+ m  x$ |- K. T6 @, q& H$ `! K3 d2 m  L
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;! t7 m  _/ f9 Y! |% @; R* `( ~
namespace 又费马达又费电
% E/ J. O7 l' ~( G  ~8 a* O5 ^4 f{
% V6 @) O/ z2 {( A" t    class Program
4 l0 b# K( W* W+ r% X8 e* z    {- A% I2 z* X' M4 `' D
        static void Main(string[] args)6 `# |1 E& r/ }
        {3 @. u- N! ~& l0 {0 C  b
            int m, n;
' L- u* M. O& e5 y' O# x            Console.WriteLine("请输入数组长度");
% Z! f& H+ h+ r5 @  f; \# w            m = int.Parse(Console.ReadLine());//m为数组的大小/ M# H) t# ?) q4 U9 k8 D9 z
            Console.WriteLine("请输入要截取数字的大小");2 E5 F# W; c' |7 {. z
            n = int.Parse(Console.ReadLine());
7 M4 g" d2 _. d$ ]* ]            int [] numw=new int
4 Y/ P$ j, \6 D0 t, ~( w6 @) \6 L; h2 }  q
&shy;&shy;&shy;;
! q1 J! t, K) V& {# Y: ?            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数' c4 J/ ?6 N- t& N( A
            {( g, w/ U# O0 Q$ c
                numw[j - 1] = j;
: g1 h+ r% Z8 L1 H' G            }3 b) }8 _) t1 E' q/ N- m, u- D
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!; C4 `# `$ S0 Y
            while (d != m - 1)" B$ w# Z% Y# @& m- C2 O  T6 k$ t
            {9 Q2 d- c/ ]$ F! q4 P1 t
                if (i == m && d != m - 1)  r4 h* n9 y4 W9 ?& M7 O
                {! m: P+ y4 @% ^# W9 N% M6 v
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
% N7 X7 T$ b7 T, [                    continue;
' s% H2 E1 Q: j  S! A                }5 B( G8 P8 e8 v- o
                else/ D3 |9 C, ?0 t6 p' \
                {# f, j% X6 U3 p
                    if (numw[i] != 0)
9 L3 C: g! Y7 @% q7 ^; E                    {" u; @' j& d3 U6 S/ L
                        i++;
6 W/ H* W" ^$ A) ?                        k++;0 s( j  q3 p) @
                        if (k == n)
' M, w- P  \' G- f( R9 l" e+ `                        {
( c$ }7 |  b6 Q4 K  I; V& P7 o                            numw[i - 1] = 0;//把在n位置数组元素的值改变了2 G, ~5 Q0 t* x3 L3 r5 [
                            k = 0;" G7 h+ Q) |. d% J. A2 `: E5 b& c
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
  }# F, h( ~) i( O5 E; u8 p$ n                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);/ U' i; E; Y+ f
                        }3 G9 ~7 B& x4 A. V2 M. R" T2 {/ @
                        else//输出暂时还没有改变数组元素的值) N5 p7 \) |0 w5 n
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 d0 F9 B+ V1 I. I/ @0 P                    }
, [$ K) w9 V$ G! ]                    else8 _; p) u' a8 ^6 p$ z
                        i++;//数组元素为0,直接跳过,不计数。。。' T+ \7 |1 [* j4 _/ h+ B, G
                }5 C. V" K, V) Q- A

. H5 s: V# ?5 D+ p7 C6 Z+ p5 R- e7 _9 Y+ [9 h/ b
            }//结束while循环
" ~0 B& Q+ b. P, h0 }2 k' q            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦! f$ b2 n' S& e! k
           
3 }9 h( Y/ I6 m. y  @                if (numw[i] != 0)
) V& I1 I2 u( o+ ]" V! S' c                    Console.WriteLine(numw[i]);
4 Z" b+ |% f  {  z4 K: Z, u           
, U5 s, W3 M  M/ m# @6 Q6 l& H            Console.ReadLine();) Z; r1 C- ?' u% U2 v7 r
        }0 t3 C1 N* z& r0 G8 h
    }
" S* r- f' G0 {}; @1 y; y% \" k& P  P  c
小甲鱼最新课程 -> 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-20 12:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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