鱼C论坛

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

猴子问题

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

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

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

x
大家好!! c! e! ?; t) o9 O
这几天我在忙着编一个问题,我用了一种方法编出来!
7 U- J  N; _2 r$ e6 p8 U  o但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!) G8 `9 o+ b9 B2 @! J: G) Q* H
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
7 i( s0 Z4 q& m6 p! {
. }. A! W- b% T* w8 f* y" @* E2 j
* \* T* x8 v8 I/ @% Q
                            题目1 T- W5 r* V* T0 F! _) O5 i0 X
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
4 S7 ~+ Y5 e- c; d; f第一种方法:利用循环链表/ z# R* j) V' M
#include<stdio.h>
6 F( r0 _) G& i- e( \; A#include<malloc.h>- S( C: o5 W- d
#define M 8            //共有8只猴子
. e$ s, x7 n2 {- w#define N 3            //数到3只时退出第三只
% G4 J3 B( P; V1 Atypedef struct monkey
* K7 b1 G$ d0 w. P" b{int number;. }. _0 y' ?+ X. Z
int flag;
* }6 ~8 _* p1 @+ x, E; X1 N- _# Cstruct monkey* next;
! F/ O8 z9 I: u# U}MONKEY;
5 W* u' j) j0 T8 H( Nmain()
4 Q; u1 {- r. W4 A{ MONKEY *head=NULL,*p,*s;
% R6 t' C1 `0 [5 m1 t) ]  int i,sum=0,count=0;, C5 u9 e3 i/ t7 @8 ^5 m
  clrscr();              //清屏0 [% h( L+ w' ?; U7 c3 a
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存, d/ Z- ?' V- y, ^1 Q
  p->number=1;p->flag=1;
4 V' ^: ?% a( D5 B3 a  v  p->next=head;
3 t# `, k4 w! i/ g5 _  head=p;
' ], t2 v7 b" B* B3 |' {  for(i=2;i<=M;i++)& a: m) l9 |3 V! _9 @1 k
    { s=(MONKEY *)malloc(sizeof(MONKEY));- K) N3 Y1 n- n4 A! E& V. h
     s->number=i;s->flag=1;$ `  Z2 W. @- E) Z/ i  Z: W9 C
     s->next=head;
& e/ y% ?- U( c- H& u1 J/ o0 \     p->next=s;p=p->next;- D- ^8 W! Y' }
    }2 s4 w, t8 W% J
    p=head;; m$ k9 q% t, J5 e* Q; A
   for(;;)* X6 W4 M6 R9 K3 u
    {if(p->flag==1)& u! M; {$ w* |# v$ [. J6 N( D' M
       count++;4 b. X, o) f% I# i+ h  e+ F
     if(count==N)7 |1 a/ v* ?0 i" q
        {p->flag=0;
, S1 g) x7 ^& x0 r; c         count=0;
, l5 V: s8 x0 S& P) V( o         sum++;}
1 ]+ ~; S  D* \5 k8 Y     if(sum==M-1). P& W. Q, \7 u& \* T) W8 P
        break;
3 q& r) v) a" ]& P0 ^- V! {0 @# W     p=p->next;
- p* S8 x. U* U3 M    }/ M6 S# x* @2 v
    p=
8 P' n) x4 b* B* K    head;
7 W, ^- H) s% N/ J# I    for(i=1;i<=M;i++)
% X/ {+ J5 s& l    { if(p->flag==1)
7 S0 w  Y  j0 B$ e" O/ x  P: j        printf("\t%d",p->number);- _# x. b" H6 D6 D
      p=p->next;! m0 S$ U# D/ l  V# l: V) ]
    }8 r' z* h1 j# o! K

& x5 k. v% g6 V. B: P% w9 `# L% I  J) V! x

% N9 E, O$ B) c) O6 B. E! f}
$ a- I6 @1 ^- U% g# y
第二种方法:数组, g2 C- g$ U. _, e
#include<stdio.h>
! y) ?5 P  Q+ j" D, _  I8 s#define M 8
7 j) K6 B' ]$ O$ B4 G% Rstruct monkey
& `! b6 d* F( R, j{int number;" }$ c$ [# u0 X' u1 f( ?- c6 ~2 v
int nextp;/ D* N/ X6 d3 s& q9 V# e' o/ b
}link[M+1];
" q; K+ ~6 G2 Y3 ~; x
7 Z8 k  ]* y$ s/ e" d5 {void main()" W$ @0 @8 b# W+ `6 X) D
{int i,count,h;
! E& F2 R; p  B+ t  Cfor(i=1;i<=M;i++)
% E( s0 ?8 W6 u. h{  if(i==M)
+ x# J, C0 H+ L1 W   link[i].nextp=1;6 n2 D1 t. @% z0 u" _2 C" d: u
   else; L4 n+ m" k2 x5 h! j4 a
   link[i].nextp=i+1;) o; Q8 ?9 K# T0 ^4 n* g* A
  link[i].number=i;
( r7 Q2 x6 r/ x" m$ ~$ L. ]7 q, g}
5 B* H' u9 F5 F- T1 x. xprintf("\n");
" Q6 S9 N" ~6 X$ |2 X/ c+ Lcount=0;: ]6 ?$ D0 y$ [/ d1 b) [" G
h=M;
* U/ b- F" F! J. @  T0 o9 Eprintf("依次退出的猴子: \n");) K# e0 L4 V; u! Y# t
while(count<M-1)
+ O3 |% t/ t/ w! {8 p7 r9 B{i=0;
* w3 A& Q6 v  v/ Swhile(i!=3)4 R% ?) z% l7 J: o: ]4 Q
{ h=link[h].nextp;
" V) {/ X' [8 Z  G; j   if(link[h].number)
/ R/ i6 a/ p8 f7 t1 a     i++;}
3 Y7 V% V# y$ I" _1 w7 X& @/ d0 R6 }! s1 c/ _
printf("%4d",link[h].number);
6 O0 R. `0 R$ f  c4 O& Dlink[h].number=0;
7 M: g# H8 O. y7 q2 }count++;
* Z3 }9 r% ~0 k( O" x; \}/ B  c- i5 v( I7 O9 ]( H
6 S5 T2 }5 w% t$ L' Q9 W
printf("\n大王是:");
9 p$ b' R! E3 A7 T. G  for(i=1;i<=M;i++)  S  W6 [* d+ J- G# [
  if(link[i].number)- `1 D$ \8 S$ z$ h: J  T2 V! z9 Y
    printf("%3d\n",link[i].number);
6 M$ e, i; @# O- R# k9 Z
) Z! A! g8 n; v$ M3 N' Z9 t( b7 Y, w. f  E/ U
}
4 q% A5 @' F; [* A6 K4 G- u1 V
第三种是普通方法for循环

2 i6 w5 z+ a6 w% d4 \( @! e#include<stdio.h>" Q9 X6 O' U2 |- k8 F9 T
void main()7 Z& z/ n9 I7 I8 v$ P7 |
{ int i,k,m,n,num[50],q,*p;1 U$ K: I) ^& [1 S/ E- W
    clrscr();! y% O/ v+ r# t5 v; n7 S% H
   printf("input number of person: n=");# e% B* i$ P7 s1 n% i- r
    scanf("%d",&n);6 P& _8 v/ }- q0 L5 ?
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只' N* F/ X4 n) I1 }
    scanf("%d",&q);
! I0 k. c! Q2 |+ A: b. M   p=num;
) \9 z& [8 p) k3 b9 z4 E- o  for(i=0;i<n;i++)
' t# i- R6 V  `/ a# k& X    *(p+i)=i+1;
+ k, q# l" \' Q) H; @# g   i=0;
% F( X. O( A0 ]5 z8 m$ f1 P3 J   k=0;
8 E. f$ T' \. r0 g& v: H   m=0;
8 L6 F" d/ V+ I% _  while(m<n-1)  r/ p6 I! H) O8 F1 L. s
   {if(*(p+i)!=0) k++;
7 b. H, G% j9 ?( l- o4 B, j     if(k==q)
& T; D, ?. l+ T# o5 n: Z      { *(p+i)=0;
4 Z# A+ J" {" J8 ]! T        k=0;
' v" V: i- N* C        m++;
) X. l0 o3 X# i3 t' W8 b; z. V4 K: r      }
! w4 [* e& u7 J- a& @. I) H% |    i++;- O* [$ W4 g6 K0 O
    if(i==n)i=0;
! J5 e4 A7 v4 G$ @   }2 a" Y% r, Z" @- b; p+ Y
  while(*p==0)p++;* S; d+ X; c3 b
    printf("The last one is NO:%d\n",*p);, ^2 H* j# Z. s; y; q( D# u
     getch();1 Z9 x7 W7 a6 N/ V1 i- U

- }2 G) o6 o  ?}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
& s( R0 n8 [* S5 G  M( T. _namespace 又费马达又费电
" a- d$ t# W- O2 P{' @9 Y1 D$ c" I, c! a" D; U. J  n
    class Program
1 r# J* |/ B& G    {
+ }6 s* _$ S! R2 Y5 S# R        static void Main(string[] args)' Q+ r  y! d, \" @2 N
        {
6 b# d, \# S* G3 O( ~+ d; s( ]            int m, n;1 l# u! w5 s$ m3 _' n1 \
            Console.WriteLine("请输入数组长度");3 }- F2 Q2 S- [' y" W
            m = int.Parse(Console.ReadLine());//m为数组的大小/ `* m9 a. t+ a! q6 ~# e) V
            Console.WriteLine("请输入要截取数字的大小");
% F: i3 r. X' Y$ a            n = int.Parse(Console.ReadLine());  Y7 j! t1 P2 @
            int [] numw=new int
' U0 l. K" l4 k  x$ X+ M5 M+ b3 D, J. @7 Z6 I
&shy;&shy;&shy;;' ~" \9 Z& x" Z% Q$ ^' y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数  F9 A$ b9 s: e9 G0 x' c
            {
! V8 L1 S# @" L- m5 P2 |                numw[j - 1] = j;
9 s8 @* l# ?- R            }: M9 o# p# g- c
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!2 T: x4 G. N2 N+ u- R* p, N2 w' L
            while (d != m - 1)
0 _; F3 Y5 n, K6 c3 D' s8 v; }            {. N+ ?7 v2 u1 y" g' f3 ~
                if (i == m && d != m - 1)
3 m7 s, `% A+ t                {
5 k9 [. K& M# c! N& N: d7 P! n6 h                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
9 R) x$ [( Q1 n0 t4 z7 H3 M, g                    continue;/ {# Y$ }! i; I1 s+ Z# f( f  G: [1 y
                }
, M9 X! O$ a4 C1 ?. b! \3 v                else5 p+ a9 T+ ^$ |. ]# a- ~
                {
3 m; `4 O4 l* c7 F4 C6 ]8 d$ f                    if (numw[i] != 0)+ H' k3 p  ]' Y% D' W
                    {
. s; P5 M# n3 k  d. s                        i++;
* ~2 c5 u  k' w4 F( o                        k++;  y- d0 d4 f5 E# b3 ^6 ]& M
                        if (k == n)
7 m/ o6 Q% D2 g" l) R3 a# I7 x                        {
* _0 A7 L/ k/ I* {* P% ~! x                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
; Z8 |* N  e6 G                            k = 0;! i9 u8 D' A* n' k7 N
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
" `& }$ Q- S1 P. g  I                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);% ^( q6 L' D2 J( k5 x: B
                        }# H4 h5 I- |9 H7 B5 C9 g
                        else//输出暂时还没有改变数组元素的值3 [+ G; {& I( {( U8 w. d
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
  Y8 N4 {0 K1 J% ~) [$ N                    }& `% x, j% k# }$ p  Q
                    else* f( K4 A( C( D$ h* q8 o' Q# k
                        i++;//数组元素为0,直接跳过,不计数。。。
# V  s6 l! y: B: B5 ?! u                }
% i3 O& f. _  I1 ?  f ; }7 Z% q) W6 q# V

. \, u' t0 P, n8 V7 r$ C9 _            }//结束while循环$ ?& X. i  s9 w5 Q" i3 c
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, P3 R! d" q. i/ W           6 v6 E9 P7 n9 L  H4 s! Y* G4 H
                if (numw[i] != 0)
+ F1 Y0 v/ o5 |7 }9 g% I                    Console.WriteLine(numw[i]);
! _7 f3 @4 g5 f5 V3 z8 Y. V" _           1 {0 ~+ t/ ?) r. U! t4 L
            Console.ReadLine();" }" f7 B( i/ e) K
        }
7 T9 ^9 ~+ |1 B% J) C- W5 a2 I; F    }' z: B, k' A9 l' I2 b8 z7 i! l
}) c2 l8 D/ J2 {( P# _
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-2-19 05:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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