鱼C论坛

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

猴子问题

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

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

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

x
大家好!
9 E0 T" R$ }5 i2 h8 j. `/ h这几天我在忙着编一个问题,我用了一种方法编出来!( Y: a& V3 f% F7 @1 c) i5 n
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
2 ?/ G  n' c9 J8 ]. r9 B& ]注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
5 v+ W1 o9 N& b3 c$ O
; W9 |5 ]0 t" L! f; P0 C8 G. b
* F$ [+ q. k" ^4 `
                            题目
( N% F; h& Z+ l5 T& g山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
: I* k8 C6 k/ A+ b第一种方法:利用循环链表
: e- P' r1 n7 _#include<stdio.h>% V: @7 ?' K: G5 z" r
#include<malloc.h>5 W3 h1 h$ J# ]* h% C; E: c
#define M 8            //共有8只猴子+ o/ [/ G. y' g. u6 \( R1 n
#define N 3            //数到3只时退出第三只! ?. q/ f; |. t/ |( T# E
typedef struct monkey2 H- |% A5 f" o2 k, @- X6 B' Q
{int number;
% N/ f. u$ Z- w% x/ }# Oint flag;
$ h7 @3 b5 E, |! t! {$ d& O- Ystruct monkey* next;
6 e4 ~$ k$ l# W1 M3 `}MONKEY;
6 W9 h2 f7 T6 k1 i0 F" r: y$ ?/ r- rmain()
' H$ P6 l1 ]! h$ f- m{ MONKEY *head=NULL,*p,*s;- i$ K. n5 \4 T  a2 W
  int i,sum=0,count=0;+ O; l' P3 r! G4 ]
  clrscr();              //清屏
! ~) p+ s* w6 G# X+ @) ?  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存' ?( d# L, x9 z$ h. k) g/ ]# K  |
  p->number=1;p->flag=1;
- ?3 |* r% x/ ~& p" \  p->next=head;  W4 G5 n" V: o0 Z
  head=p;
6 X1 E: ~5 I% O& b- [! P7 j  for(i=2;i<=M;i++)
1 o6 {2 S8 t/ o    { s=(MONKEY *)malloc(sizeof(MONKEY));+ f, I5 W& V' H1 z/ t
     s->number=i;s->flag=1;
' s% R% C( }) m     s->next=head;
2 t4 L; e: c' f; u  }     p->next=s;p=p->next;2 w( E* U  E) J0 @( c9 T1 J4 n
    }. A! e; ?  E4 \6 ^6 n
    p=head;+ P9 W3 M& D( \, ~! c% E: f
   for(;;)
* e) a" V  c5 y$ K1 p    {if(p->flag==1)9 t" C$ p6 {! g
       count++;$ ?1 ]6 v  {9 o1 c
     if(count==N)
2 J% Y( k# z7 T" H        {p->flag=0;
; M$ t4 w5 h& L. U% A; ?) @8 w         count=0;
2 ~( x; }- L4 i5 {) ]         sum++;}: |4 z) V( s+ [# ?) u
     if(sum==M-1)" E1 O; B6 d4 Q! H
        break;# G( G' E! u( a' Y4 \7 n  O# i
     p=p->next;
0 Y, u9 Q9 u5 H5 e3 [$ K" t1 z    }
+ Y: z, P, {; b6 ]# K# E8 G# Y    p=9 E# z; p1 P( u% S, B( ]
    head;
" ?) v! f, n: P1 ^- K  d    for(i=1;i<=M;i++)
5 s; a  ~2 e2 b- W; ]* y    { if(p->flag==1)
, c) Q) b4 y2 u. U) t( |6 @( P; q        printf("\t%d",p->number);7 L1 t2 Q# \/ C$ @) Y' O
      p=p->next;! ~, f  m0 K& M6 }. ^+ A
    }* e- a/ y2 L, {
" l% m& v; `$ Y+ `9 M6 I

; Y: B6 `# g/ s/ F* u2 ~7 ^: Y% C
2 C( Q9 |. J6 r. e" c! k$ f}

6 Z. ~( I+ ~+ o/ t& E$ g- G5 o9 Y第二种方法:数组
) a+ y6 E2 u# S+ n' |; d#include<stdio.h>
( q7 `! r& N) C+ V#define M 84 f- [1 Q8 ~! E( u1 e( B
struct monkey* V3 x5 C! n/ c+ l; g$ o
{int number;  L+ M1 i* w5 P+ E4 Q% `
int nextp;6 {5 {0 i: l" p+ |8 j- e* h8 L
}link[M+1];
' i$ f9 @6 N" p/ z
/ k) E" s( S, P4 pvoid main()
- w3 ~) [0 |8 Q) R  S{int i,count,h;& A* D  J  w* W  z9 f; j% s
for(i=1;i<=M;i++)
$ F' B; g  W" m) n2 l5 _  g{  if(i==M). d6 j! _" R6 D, X1 w
   link[i].nextp=1;
2 @: ^2 T3 q* V4 Y6 b   else$ e- E# v4 R% u9 S
   link[i].nextp=i+1;
. r% V3 @* [9 P, Z  link[i].number=i;
+ _1 D4 R, a+ e2 _1 I) o}
' p' K! {. T3 i, Kprintf("\n");
- `# Y* w& Q* Icount=0;
* s1 v6 A8 ]; W, x- \h=M;
- C! s9 z6 D# |# o9 rprintf("依次退出的猴子: \n");  j3 m: c, {9 }' z0 l
while(count<M-1)
* k1 Z! z. I, {1 D/ ?! l{i=0;
- q1 _1 u7 r5 C' E' jwhile(i!=3)3 k. C) ]8 Q: G5 z9 N, O; S4 _
{ h=link[h].nextp;
" K. S0 C; s6 w1 r! y8 K   if(link[h].number)- R0 k" C- O( Y
     i++;}
: q2 e& r( J! f* w3 y
2 M# O; s0 p% f/ _3 I3 U. Hprintf("%4d",link[h].number);
3 D' s8 ]. X4 U$ p7 ulink[h].number=0;
  L# ]. E$ S/ e- ~: I5 L2 Gcount++;- Q7 e0 E/ N( N! a5 i
}* C2 S4 E5 F4 B# C" Y. j
, g( l$ M% M5 o$ Q+ N6 m
printf("\n大王是:");3 g3 b3 K2 K  ?  D) P
  for(i=1;i<=M;i++)1 c/ ^# @: T9 s
  if(link[i].number)
# R0 g) k$ P' y& x+ d    printf("%3d\n",link[i].number);
% d+ K" |, P; K( k1 D6 G  e- ~# H) h- _) B# C) b1 M6 O
- J# D& {+ Q! ~, N) G; \
}
; {* A/ T7 Q2 i3 v' \1 T& A' v
第三种是普通方法for循环
7 M- @3 r/ ~$ N. m( R
#include<stdio.h>
) y  G- t2 r) m! _0 _void main()* c8 I( W7 ~5 g: s* X
{ int i,k,m,n,num[50],q,*p;
' M5 b2 Z. K6 P* q  i9 J1 h4 ~    clrscr();
( S5 [  O1 z% w$ N2 Z7 a   printf("input number of person: n=");2 N# Y- S: z$ {& {# v
    scanf("%d",&n);
; c6 n8 `# M" M3 C- z% Nprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
" q. b/ C2 y) v: s5 P    scanf("%d",&q);
& a5 \' f* i9 _- M) D  K0 m! D9 S# ~   p=num;' H" x4 j. q* U9 l  Z1 K
  for(i=0;i<n;i++)5 A3 g' O3 \0 d: s" S; t, y' u
    *(p+i)=i+1;
5 l  W1 C: `3 X/ W0 f/ T  Y   i=0;, j+ {7 ~7 L; N2 B$ `
   k=0;
# ?5 A7 {+ l, h/ L. B   m=0;5 F, }- c! g% Z4 a( u: w
  while(m<n-1)
" A5 P% i! c$ |  [4 s   {if(*(p+i)!=0) k++;
- z; N3 P0 P  f     if(k==q)! Y, C0 _: i7 s  h4 u
      { *(p+i)=0;
  W9 G* B; [+ v, q, r+ v0 t        k=0;, _1 d& i. w6 Z4 j1 {  A. ~
        m++;
' K- r2 L2 i0 `' Z. W6 _5 f      }
3 [; O- F6 L1 w% i  h3 ]. S  @    i++;
/ ]) r6 {, q7 c& b1 Y% S# X# N. K    if(i==n)i=0;
6 Y: t9 O% ~7 ^6 G) \   }" v5 h3 y; R( y" X
  while(*p==0)p++;
" e% r- c) I0 ^6 \& i5 y    printf("The last one is NO:%d\n",*p);1 b  @5 x& r$ y
     getch();, s3 j1 L4 v, {/ x' E  {$ X0 p

  O) U4 z/ d% o# i2 W}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;4 ~1 \3 w9 }/ Q
namespace 又费马达又费电7 c3 {) Q. Q" C7 s* K
{$ h1 z" ]! ^9 o- ^$ P
    class Program
6 c! L# m6 i7 ^( r( i7 u3 ?. x    {
7 |4 D" k. l, @5 [/ c        static void Main(string[] args)8 X1 s5 }$ \; G4 U$ w$ O4 {  i
        {4 u% [7 ~& F4 ^' i3 A
            int m, n;
9 A! M% T% U+ [4 Z" w/ m            Console.WriteLine("请输入数组长度");
4 W9 R4 @; l8 ~5 T4 N' a% j            m = int.Parse(Console.ReadLine());//m为数组的大小. }9 Q; O! m$ V" Z
            Console.WriteLine("请输入要截取数字的大小");
4 j7 w$ p% o8 ~            n = int.Parse(Console.ReadLine());9 s) `1 h1 d3 X, C* `1 ^
            int [] numw=new int
" W8 N  M9 a& ?4 A4 W' J" i" k" ]  i9 W" E. X$ d
&shy;&shy;&shy;;
; }1 N6 m( N1 w! b; d            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
8 d3 g5 ~; y+ H4 G# l: G* r. o            {4 k# ?1 j8 Q' D8 v: X; B
                numw[j - 1] = j;
' ~4 [$ ?6 i4 }6 c            }7 i/ W5 o0 U) g7 E
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!2 p' y. y/ }" ~+ S
            while (d != m - 1)% @5 c" i# q  k2 J! v) Q9 f
            {
7 i; H( f% l% T3 ^2 M9 e' u9 V                if (i == m && d != m - 1)
# W! H) P% _) d- n% Z                {# u7 N' z; ]; ~* ^+ T& L
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
4 a: v. K% c& e  ?3 z7 K                    continue;
  Y" i6 V$ ]7 L1 o                }3 V9 J6 S0 m% ~& ]! E2 R
                else
3 W( v6 z- d& v                {% \( p( Q) i5 n+ N% G
                    if (numw[i] != 0)
8 l1 A3 a: W+ a0 `/ T                    {( ^! q5 T' d6 V2 @( O
                        i++;
5 F) M: E% d" \  z( R/ C                        k++;1 T+ ~% U9 n( g8 E. K2 ?: J. Q
                        if (k == n)5 b- [3 u0 S: g! N! ?# Q* ~
                        {
3 q% s0 I0 F1 `2 v. S+ x( Q                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
/ M- f  Z9 h7 u0 c! z                            k = 0;" a# p  G- W# z& C& d
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 y1 m5 U, u) O7 z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' K1 a, u* {- T, q                        }6 h$ P7 m6 J$ n, f, n2 p/ t1 h& w
                        else//输出暂时还没有改变数组元素的值1 h& A, B3 \* x" e  N5 @$ c
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 f/ G- v* s, f8 P                    }
" I$ ]1 }/ u4 }( u3 y                    else
. L9 G! E, P7 d+ ?( u8 F9 v                        i++;//数组元素为0,直接跳过,不计数。。。6 r- Y7 L# R( J
                }
) \, ^7 S& O& n4 ~; W % h  n! ~- x7 ]. m+ A5 z4 v' f
7 L" n1 L; j1 m/ F1 p1 F! b
            }//结束while循环" n1 J8 O. i. l2 Q
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
5 N7 |( d( ~+ d& S# B8 n& ]( q           ! z7 v6 ~5 D* J" |8 `
                if (numw[i] != 0)
% I% t+ k3 }& r: u                    Console.WriteLine(numw[i]);* Z  t! r+ ~* U6 Y8 N1 e9 N7 u: V1 O
           
% V4 f% r  m9 [  }5 G4 ^4 D            Console.ReadLine();# o' ~5 b/ ?( I1 m0 F; b
        }
0 [3 o1 E( g( W! W: Y0 W    }
6 L- j- M& Y6 U/ T7 G6 C7 W+ o) q+ }% }}
* h  A0 J9 m' E9 c. C2 g
小甲鱼最新课程 -> 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-2-16 08:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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