Lesson-10.md

Lesson 10 Josephus ring 约瑟夫环

#include <stdio.h>

#define ALL_NUM    	100
#define COUNT_NUM	3
#define OUT_NUM		3

/* people id array such as (1,2,3,4,5,6) */
int people[ALL_NUM];

int main(void)
{
	int left;	/* left people number */
	int pos;	/* which pos */
	int step;	/* which step */
	int i;

	int counter = 0;

	left = ALL_NUM;
	pos = 0;
	step = 0;

	/* init id as 1,2,3,4,5,6 */
	for (i = 0; i < ALL_NUM; i++)
		people[i] = i + 1;

	/* if there is still people in queue */
	while (left > 0)
	{
		/* pos++?  step++?   left--? */
		if (people[pos] > 0)
			step++;

		if (step == OUT_NUM && people[pos] != 0)
		{
			printf("%d out \n", people[pos]);
			people[pos] = 0;
			left--;
		}
		
	#if 1
		pos = ++pos % ALL_NUM;
		step = step % COUNT_NUM;
	#else	
		pos++;
		if (pos == ALL_NUM)
			pos = 0;
		
		if (step == COUNT_NUM)
			step = 0;
	#endif
	}

	return 0;
}

语法知识点

• 函数设计 function
• 数据驱动编程

课堂讨论

• pos 和 step 变量，每次赋值用 if 和 直接赋值，在执行效率有什么不同？
• 在这个算法实现中，留在环里面的人越少，无效的比较次数越多，有什么办法可以优化算法？
• 如何使用数组实现在课堂讨论中想到的优化算法。

课后练习

• 增加一个变量，用来统计在以上算法执行过程中比较的次数。
• 已知2012年1月1日是星期日，请打印出全年的月历。要求用到函数，数组和循环。
• 用户输入10个数字，对它们进行排序，要求把所有奇数排前面，所有偶数排后面。

名人名言

• Rob Pike (Go语言之父，和Ken Thompson一起设计了UTF-8编码格式，现Google首席工程师。)
  • “Data dominates. If you’ve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.”
  • “数据压倒一切。如果已经选择了正确的数据结构并且把一切都组织得井井有条，正确的算法也就不言自明。编程的核心是数据结构，而不是算法。”
  • “给我看流程图而不让我看（数据）表，我仍会茫然不解；如果给我看（数据）表，通常就不需要流程图了；数据表足够说明问题了。”