数三退一的问题解决（C语言和Java实现）

1 概述

数三退一的问题指的是一堆小朋友手牵手围成一个圈，从第一个小朋友到最后一个小朋友分别报数，报到数字“3”的小朋友要及时退出这个圈，剩下的人继续围成一个圈，然后从那个退出的小朋友的下一个开始重新从“1”开始报数，“1，2，3，1，2，3……”，直到圈中只剩下一人为止，求出剩下的这一人的编号。

2 问题决解

采用循环链表的方式进行解决，KidCircle基于循环链表实现把一个个kid连起来。首先从第一个Kid开始（即KidCircle的head成员）计数，Kid一直向后移动，数到3将调用删除方法将该Kid删除，并把计数器重置为0，直到KidCircle的size为1时，停止数数，打印出head的id即可。

3 代码实现

3.1 C语言

采用头文件公开一些公用方法和数据类型，具体实现的源代码文件和main函数文件分离

头文件kidcircle.h

/* kidcircle.h */#ifndef KIDCIRCLE_H_#define KIDCIRCLE_H_/* DataType */struct Kid_ {	int id;	struct Kid_ *left;	struct Kid_ *right;};typedef struct Kid_ *Kid;struct KidCircle_ {	int size;	Kid head, tail;};typedef struct KidCircle_ *KidCircle;/* public interface *//* * 功能：创建一个KidCircle类型  * 参数：无 * 返回值：KidCircle  */extern KidCircle new_kidcircle();/* * 功能：在kc中增加指定数目num的孩子  * 参数：kc是已经初始化的 KidCircle类型的指针，num需要增加的孩子数目  * 返回值：无  */ extern void add_kid(KidCircle kc, int num);/*  * 功能：使孩子K退出kc * 参数：kc是已经初始化的KidCircle类型的指针， k出队的孩子 * 返回值：无  */extern void del(KidCircle kc, Kid k);/* * 功能：销毁动态申请的内存  * 参数：kc是已经初始化的 KidCircle类型的指针 * 返回值：无  */ extern void dispose(KidCircle kc);#endif
接口实现文件kidcircle.c
/* kidcircle.c */#include <stdlib.h>#include <stdio.h>#include "kidcircle.h"static Kid new_kid(){	static int cnt = 0;	Kid k = (struct Kid_*)malloc(sizeof(struct Kid_));	k->id = cnt++;	k->left = NULL;	k->right = NULL;	return k;}static void dispose_kid(Kid k){	free(k);}extern KidCircle new_kidcircle(){	KidCircle kc = (KidCircle)malloc(sizeof(struct KidCircle_));	kc->size = 0;	kc->head = NULL;	kc->tail = NULL;}static void dispose_kidcircle(KidCircle kc){	free(kc);}static void add(KidCircle kc){	Kid k = new_kid();	if (kc->size == 0) {		kc->head = k;		kc->tail = k;		k->left = k;		k->right = k;	} else {		k->right = kc->head;		kc->head->left = k;		kc->tail->right = k;		k->left = kc->tail;		kc->tail = k;	}	kc->size++;}extern void del(KidCircle kc, Kid k){	if (kc->size == 0) {		PRintf("the kidcircle has no kid");		return;	}	if (kc->size == 1) {		kc->head = kc->tail = NULL;	} else {		k->left->right = k->right;		k->right->left = k->left;		if (k == kc->head) {			kc->head = k->right;		} else if (k == kc->tail) {			kc->tail = k->left;		}	}	dispose_kid(k);	kc->size--;}extern void add_kid(KidCircle kc, int num){	int i;	for (i = 0; i < num; i++) {		add(kc);	}}extern void dispose(KidCircle kc){	Kid k = kc->head;	while (kc->size > 0) {		del(kc, k);	}	dispose_kidcircle(kc);}
main函数文件main.c
#include <stdio.h>#include <stdlib.h>#include "kidcircle.h"int main(int argc, char *argv[]){	KidCircle kc = new_kidcircle();	add_kid(kc, 500);	Kid k = kc->head;	int cnt = 0;	while (kc->size > 1) {		cnt++;		if (cnt == 3) {			cnt = 0;			del(kc, k);		}		k = k->right;	}	printf("%d", kc->head->id);		dispose(kc);	return 0;}
3.2 java语言
/* CountThree.java */public class CountThree {	public static void main(String[] args) {		KidCircle kc = new KidCircle(500);		int cnt = 0;		//mark		Kid k = kc.getHead();		while (kc.getSize() > 1) {			cnt++;			if (cnt == 3) {				kc.delete(k);				cnt = 0;			}			k = k.getRight();		}		System.out.println(kc.getHead().getId());	}}class Kid {	private int id;	private Kid left;	private Kid right;	public Kid(int id) {		this.id = id;	}	public void setLeft(Kid k) {		left = k;	}	public void setRight(Kid k) {		right = k;	}	public int getId() {		return id;	}	public Kid getLeft() {		return left;	} 	public Kid getRight() {		return right;	}}class KidCircle {	private int size = 0;	private static int cnt = 0;	private Kid head, tail;	public KidCircle(int num) {		for (int i = 0; i < num; i++) {			add();		}	}	public void add() {		Kid k = new Kid(cnt);		if (size == 0) {			head = tail = k;			k.setLeft(k);			k.setRight(k);		} else {			/*tail.setRight(k);			k.setRight(head);			k.setLeft(tail);			head.setLeft(k);			tail = k;*/			k.setRight(head);			tail.setRight(k);			head.setLeft(k);			k.setLeft(tail);			tail = k;		}		size++;		cnt++;	}	public void delete(Kid k) {/*		System.out.println(k.getId());		System.out.println(size);*/		if (size <= 0) {			System.out.println("The KidCircle has no Kid!!!");			return;		}		if (size == 1) {			head = tail = null;		} else {			k.getLeft().setRight(k.getRight());			k.getRight().setLeft(k.getLeft());			//important			if (k == head) {				head = k.getRight();			} else if (k == tail) {				tail = k.getLeft();			}		}		size--;	}	public int getSize() {		return size;	}	public Kid getHead() {		return head;	}	public Kid getTail() {		return tail;	}}