问题描写叙述:数组
在《josephus Problem 0基础(使用数组)》中。咱们提出了一种最简单直接的解决方式。spa
但是,细致审视代码以后。发现此种方案的效率并不高,详细体现在。当有人出局时,遍历数组仍需要对其进行推断,code
这无疑作了无用功。减小了代码效率。在人数多时尤为明显。blog
解决方式:ip
当有人出局时,考虑将当前出局的人的前一我的(未出局)的下一我的置为当前出局的下一我的(未出局)。it
这样,便确保了每次对counter的添加都是有效的。遍历到的人都是尚未出局的。大大提高了程序的效率。这事实上运用了链表的思想。io
代码:class
#include <stdio.h> /*total people number*/ #define ALL 100 /*people leave when count to left_counter*/ #define left_counter 3 /*next Array record the next people's position*/ int next[ALL]; /*init next array*/ void initNext() { int i = 0 ; for (i = 0; i < ALL; i++) { next[i] = (i+1) % ALL; } } /*print next array*/ void printNext() { int i = 0; for (i = 0; i < ALL; i++) { printf("%d ", next[i]); } printf("\n"); } int main(void) { initNext(); int left = ALL; /*init total left number*/ int counter = 0; /*init counter*/ int i = 0; /*init array index*/ int prev = All-1; /*init prev*/ while (left > 0) { counter++; /*if counter == left_counter , people out, set next[prev] = next[i] counter = 0 left-- **/ if (counter == left_counter) { left--; printf("%d is out\n", i+1); counter = 0; next[prev] = next[i]; printNext(); } /*change prev, increase index*/ prev = i; i = next[i]; } printf("problem finished!\n"); return 0; }