猴子选大王
#include<stdio.h>
#include<stdlib.h> //使用calloc()函数
void FindKing_pointer(int,int,int*);//移动指针法找大王
void FindKing_MoveArray(int,int,int*);//移动数组法找大王
void Initialize(int,int*);//初始化数组
int main()
{
int m,n,*ptr;
printf("输入猴子数与淘汰时报的数\n");
scanf("%d %d",&n,&m);
ptr=(int *)calloc(n,sizeof(int));
Initialize(n,ptr);
FindKing_pointer(m,n,ptr);
Initialize(n,ptr);
FindKing_MoveArray(m,n,ptr);
free(ptr);
return 0;
}
/*
在数组中依次填入1,2,3,4,…
*/
void Initialize(int n,int *ptr)
{
int i;
for(i=0;i<n;i++)
ptr[i]=i+1;
}
/*
循环一次指针向后移一位,所指元素不为0时计数器加1.
移动指针,当计数器数到m时将指针所指元素设为0.
*/
void FindKing_pointer(int m,int n,int *ptr)
{
int i,count,*ptr2;
count=n-1; //count=0时终止循环
ptr2=ptr; // 移动ptr2进行查找
for(i=0;count;ptr2++)
{
if(ptr2==ptr+n)
ptr2=ptr;
/*指针所指元素不为0时计数器加1.*/
if(*ptr2)
i++;
/*计数器数到m时将指针所指元素设为0*/
if(i==m)
{
*ptr2=i=0;
count--; //用于终止循环
}
}
/*最后不为0的元素的值即为大王的编号*/
for(ptr2=ptr;;ptr2++)
{
if(*ptr2)
{
printf("第%d个猴子是大王\n",*ptr2);
break;
}
}
}
/*
计数器i循环时自增,当i=m时用j标记当前数组元素下标
并该移动元素后的其它元素,同时i=0,数组长度n--,n=1时终止循环
最后数组首元素的值即为大王的编号
*/
void FindKing_MoveArray(int m,int n,int *ptr)
{
int i=0;
int j,k;
for(j=0;n-1;i++)
{
if(i+1==m)
{
j=(i+j)%n;
if(n-1-j)
for( k=j+1;k%n;k++) //移动j元素后的其它元素
ptr[k-1]=ptr[k];
n--;
i=-1;
}
}
printf("第%d个猴子是大王\n",*ptr);
}
----------------------------------------
运行结果(VC6.0环境下):
输入猴子数与淘汰时报的数
3 2
第3个猴子是大王
第3个猴子是大王
Press any key to continue
输入猴子数与淘汰时报的数
5 2
第3个猴子是大王
第3个猴子是大王
Press any key to continue
输入猴子数与淘汰时报的数
100 50
第95个猴子是大王
第95个猴子是大王
Press any key to continue
-------------------------------------------------------------------------------------------
总结:
选大王程序用了两种算法实现,第一种为最常规和最简单的算法,但是将指针从数组尾移动到数组头也很麻烦;第二种算法是偶尔想到的,开始感觉是最简单的,不用将指针从数组尾移动到数组头这样来回移,只需每次将数组长度缩小.但是编程实现时发现要将计数器与对应元素联系起来不简单,想了好久再引入变量j才将计数器与对应元素联系起来.
后来还想到一种算法,用链表,但是将指针从链表尾移动到链表头也很麻烦,于是又想到将链表首尾连起来.但这两种算法比以上两种更复杂,唯一的好处是熟悉链表的基本操作.
查书后发现只有第二种算法算是原创,其它几种书上都有.
2006-11-28 22:16
