论文部分内容阅读
◆摘 要：本文主要考虑二级制在有限的递归中的一点巧用，递归法一般是针对十进制自然数，本文旨在给学生延拓思维。
◆关键词：二进制；递归；博弈策略
一、引言
我们将通过介绍一场人机博弈的方式来引入二进制的一个应用。关于二进制的介绍可以在很多计算机入门课程中找到，例如[1-4]。以下我们先简单介绍博弈规则。
假设计算机给出一串长度为n的0，1字符，博弈方式为玩家删除最右端字符。当玩家删除的字符为0时，其它字符右移一位，且电脑将在字符串的左边随机生成一个字符0或者1；当玩家删除的字符为1时，其它字符右移一位，且玩家可自行选择在左端添加0或者1。若在某一时刻所有的字符全为0，则玩家获胜。
二、博弈策略及其分析
顯然，若在某一时刻所有的字符全为1，则在接下来的n次删除字符后玩家均在左端添加0即可。
我们接下来将把每n次操作看作一组，则每一组操作后，实际上我们可以看作是直接对原有每个位置的字符进行一次替换。当原有字符为0时，由电脑随机决定替换为0或者1；当原有策略为1时，玩家可自行决定替换为0或者1。
我们可以将长度为n的0，1字符看作是二进制表达下的一个数，该数的范围在[0，2n-1]之间。每一组操作中，字符串的替换顺序时从右向左。
我们的博弈策略如下：每一组操作中，我们观察电脑的替换.此时有以下两种情形：
情形一：若电脑始终将0替换为0，则我们也将1替换为0，这样一组操作后自然得到所有字符全为0。
情形二：若在某个位置，电脑将0替换为1，则在该位置之后的操作中我们始终将1替换为1。
注意到，如果在某一组操作中出现情形一，则玩家已经获胜结束博弈过程。因此我们主要分析情形二。而实际上情形二出现时，我们一组操作后二进制所表达的数字是严格递增的。注意到长度为n的0，1字符看作是二进制表达下数的范围在[0，2n-1]之间，因此若持续出现情形二，则一定在经过若干次操作后，我们可以得到全为1，此时下一组操作中玩家全替换为0即可获胜。
三、小结
该策略中，我们比较核心的思想是通过递归的方法来得到严格递增的字符串，然而字符串所表达的数有上界，故而必然可以达到。
参考文献
[1]谭浩强.C语言程序设计（第二版）[M].清华大学出版社，2009.
[2]胡泉，谢芳.C语言程序设计[M].华中科技大学出版社，2009.
作者简介
钱文华，重庆师范大学数学科学学院，重庆市沙坪坝区大学城校区。
◆关键词：二进制；递归；博弈策略
一、引言
我们将通过介绍一场人机博弈的方式来引入二进制的一个应用。关于二进制的介绍可以在很多计算机入门课程中找到，例如[1-4]。以下我们先简单介绍博弈规则。
假设计算机给出一串长度为n的0，1字符，博弈方式为玩家删除最右端字符。当玩家删除的字符为0时，其它字符右移一位，且电脑将在字符串的左边随机生成一个字符0或者1；当玩家删除的字符为1时，其它字符右移一位，且玩家可自行选择在左端添加0或者1。若在某一时刻所有的字符全为0，则玩家获胜。
二、博弈策略及其分析
顯然，若在某一时刻所有的字符全为1，则在接下来的n次删除字符后玩家均在左端添加0即可。
我们接下来将把每n次操作看作一组，则每一组操作后，实际上我们可以看作是直接对原有每个位置的字符进行一次替换。当原有字符为0时，由电脑随机决定替换为0或者1；当原有策略为1时，玩家可自行决定替换为0或者1。
我们可以将长度为n的0，1字符看作是二进制表达下的一个数，该数的范围在[0，2n-1]之间。每一组操作中，字符串的替换顺序时从右向左。
我们的博弈策略如下：每一组操作中，我们观察电脑的替换.此时有以下两种情形：
情形一：若电脑始终将0替换为0，则我们也将1替换为0，这样一组操作后自然得到所有字符全为0。
情形二：若在某个位置，电脑将0替换为1，则在该位置之后的操作中我们始终将1替换为1。
注意到，如果在某一组操作中出现情形一，则玩家已经获胜结束博弈过程。因此我们主要分析情形二。而实际上情形二出现时，我们一组操作后二进制所表达的数字是严格递增的。注意到长度为n的0，1字符看作是二进制表达下数的范围在[0，2n-1]之间，因此若持续出现情形二，则一定在经过若干次操作后，我们可以得到全为1，此时下一组操作中玩家全替换为0即可获胜。
三、小结
该策略中，我们比较核心的思想是通过递归的方法来得到严格递增的字符串，然而字符串所表达的数有上界，故而必然可以达到。
参考文献
[1]谭浩强.C语言程序设计（第二版）[M].清华大学出版社，2009.
[2]胡泉，谢芳.C语言程序设计[M].华中科技大学出版社，2009.
作者简介
钱文华，重庆师范大学数学科学学院，重庆市沙坪坝区大学城校区。