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;	}}