觉得这是种找存在感的帖子的人 请笔下留情

只是平时写一个程序很难，思绪乱飞，脑袋里觉得是这样的，可敲代码的时候，又各种疑问
琢磨了好几天，总算是把这个题目的逻辑关系搞清楚了，觉得这样才算是写程序，才把自己的所思所想的过程记录下来  
一个思考的过程，望大家予以指正


题目名称：蝈蝈式的记分

内容描述：

蝈蝈小朋友刚刚学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用 0-9 这十个数字，所以当比赛选手得分超过 9 的时候，他会用一个 X 来表示 10 完成记分。但问题是，当记录为“ X 3 5 ” 的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。

因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢～于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。

需要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。

输入数据：

以 point.in 为输入文件，文件中首行只有一个整数 M ，表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录，第一行是一个整数 N(N<=1000) 表示当前这个记录中有多少个字符，第二行就是具体的 N 个字符表示记录的分数。

输出数据：

相应的内容将输出到 point.out 文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用 ":" 分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以” Unknown “一个单词独占一行表示。

输入和输出结果数据样例：

输入样例


3

23

9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1

25

9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4

43

7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1


输出样例


21:17

24:22

21:3

Unknown

21:14

20:22

21:23

21:16

21:9

[ 本帖最后由 zhu224039 于 2014-6-27 02:51 编辑 ]

首先数据从后向前进行猜测
因为要结束一场比赛,赢的一方是最后得分的一方
令countA 代表胜方
  countB 代表负方


win规则
countA在21分的时候拿下比赛 即:
countA==21 and  countA-countB>=2

countA在大于21分的情况下拿下比赛,则必须有countA-countB=2 即
countA>21 and  countA-countB=2

综合起来就是:
(countA==21 and  countB<=19) or （countA>21 and  countA-countB=2）


unknow规则
到达获胜条件 countA>=21 的时候

countA=21时
对上面win情况对countA-countB 进行取反 可知道 countA-countB<2  
在-1=<countA-countB<=1的时候 两者未能分出胜负将它排除后可以得到 即：
countA=21时  countA-countB<-1时  unknow

countA>21时
对上面win情况进行取反  可知道 countA-countB!=2
对上述条件进行分析
-1<=countA-countB=<1的时候 两者未能分出胜负 可以继续比赛 从countA-countB!=2中 去掉这个条件可以得到
countA-countB<-1 和  countA-countB>2 即：
countA>21时 (countA-countB<-1) or (countA-countB>2) 时  unknow
综合起来就是：
(countA=21 and countA-countB<-1)  or (countA>21 and ((countA-countB<-1) or (countA-countB>2)))

上述win 和 unknow 条件分析总结得出
if (countA==21 and  countB<=19) or （countA>21 and  countA-countB=2）
      win;
if (countA=21 and countA-countB<-1)  or (countA>21 and ((countA-countB<-1) or (countA-countB>2)))
      unknow

上述对于程序的接受和不接受的结果条件判定结束

下面进行程序的运算逻辑部分分析：
令a[n] 表示蝈蝈记录的比赛数据
如果整个数据都不存在x的情况下 统计计分为:
令f(a)表示countA的得分情况，f(b)为countB的得分情况则计分方法的定义为：

f(a)=a[n]+a[n-2]+a[n-4]......a[n-i]   (i为偶数集合)
f(b)=a[n-1]+a[n-3]+a[n-5]......a[n-d] (d为奇数集合)

存在x的情况下：
在计分时候要对x的位置进行探查，探查方法为每次计分的时候探查当前位置的前一个元素是否为x或者首尾部是否为x
令当前处理的数据位置为i
当i=n or  i=0时  
它就代表的是10
当i!=（n,0)时
需判断a[i-1]是否是x

对数据中x分数记录的行为定义为：
令a[i]为x所处的位置，记录的分数f(i)  则
        10             分数就为10
f(i)=   
        10+a[i+1]      分数超过10

f(i)=10时  分数记录是和不存在x的情况的时候是一样的

f(i)=10+a[i+1]时  
令p(a)表示已对countA进行的计分总数
  p(b)表示已对countB进行的积分总数
由于x出现的位置可能在p(a)或者p(b)当前位置的前一位置上 令i表示当前位置
x在p(a)当前 前一位置上：
p(a)=a[i]+a[i-1]=a[i]+10
因为i和i-1都被计分了，也就是多消耗了一个元素，调整i的值为 i-1 进入下一次计分

x在p(b)当前 前一位置上：
p(b)=a[i]+a[i-1]=a[i]+10
同上也要调整i的值为 i-1，进行后续的计分工作

计算分析完毕，分析算法步骤：
要解决的问题：
A：因为x的存在使得计分分两种情况 ，要分别对这两种情况进行猜解 所以进行一种猜解时，要保存当前状态，好为后面的猜解保存现场，选择那种数据结构进行猜解呢
    A：数组
    B：链表
    C：二叉树
    鉴于鄙人数据结构知识忘记的差不多了，脑袋里就这么几个数据结构了
二叉树 来存储是具有可能性的，因为他有两个边 可以代表 x的分叉  这个我只是略为的想了一下 还不成熟
数组相比链表来说  在这个程序里，数组要适用点，因为不动态嘛  你懂得  那就选数组了
数组数据结构 又有堆栈  队列  等等操作方式 选哪个呢 出现一个x我们就得放入一个现场  先放入的现场最后猜解，满足先进后出的特征，栈具有这个特征，那么就选栈
结论：
选择栈的操作方式对x的分支情况进行猜解

B: 如何控制countA计分了 接着就是countB计分 在没有x的情况下可以用奇数偶数来判断 现在有了x的存在奇数偶数 计分链条的奇偶关系可能会被破坏
    选择一个开关是可以解决这个问题的 令flag=0 countA计分 flag=1 countB计分

C: 如何对x有多少个如何来统计呢
   一个x对应栈中的情况 所以栈是对x的最好记录

D：如何控制a[n]元素的下标呢，在猜解成功后如何处理下标？
   令当前下标为i
   由于进行猜解过程中，i值是变化的，栈中存放的i只能记录现在猜解的位置，如果猜解成功i的值怎么办 猜解结果怎么办？
   很明显需要一块地方来存放这些结果 由于5局3胜制 说明这个比分记录最多5条 每条记录要记录猜解成功的数据countA countB 猜解成功后的i值
   由于对x的猜解 可能出现多种win的比分情况  还需要一个值来指示 是否只成功了一次 出现多次成功地情况就unknow 猜解失败
   所有要建立一个 array[5][4]的数组 记录结果

运算过程分析结束

[ 本帖最后由 zhu224039 于 2014-6-27 01:31 编辑 ]

伪代码奉上：
数据
array[5][4]
a[n]={比赛计分的集合,将有x的地方用10替换}
flag=0
栈的空间这个定义为多少呢，如果用递归来做的话估计也会让系统内存消耗完而崩溃 就搞个4096把 管它崩溃不崩溃
zhan[4096]

flag=0 i=0
for(j=n-1;j>=0;j--)
    if (countA==21 and  countB<=19) or （countA>21 and  countA-countB=2）  成功
            array[i][0]=countA;
            array[i][1]=countB;                    保存猜解成功的结果
            array[i][3]=j;                         保存猜解成功后的位置
            array[i][4]+=1;                        对猜解成功的次数计数
            if(栈不空)
                                                                     恢复现场进行下一次的猜解
                    pop j;pop countB; pop countA;
                    if(flag=0) flag=1                                 改变flag 让恢复的现场 形成 10+a[j+1]的效果
                    if(flag=1) flag=0
                    continue;
            if(栈空 and  array[i][4]>1 )                          多次成功 打印unknow  猜解失败
                    print      unknow   exit;
             if(栈空 and  array[i][4]=1 )                         猜解成功 恢复j值 继续猜解
                   i++;  j=array[i][3];continue;     
    if (countA=21 and countA-countB<-1)  or (countA>21 and ((countA-countB<-1) or (countA-countB>2)))  失败
            if(栈空 and  (array[i][4]=0 or  array[i][4]>1)  )     栈空下 没有猜解成功 或多次成功  猜解失败 退出程序
                    print      unknow
                    exit;
            if(栈空 and  array[i][4]=1 )                          栈空  猜解成功 恢复j值继续猜解  因为对结果的判定有两个入口所以要两次判断
                   i++;  j=array[i][3];continue;
            if(栈不空)                                            恢复现场进行下一次猜解
                pop j;pop countB; pop countA;
                if(flag=0) flag=1                                 改变flag 让恢复的现场 形成 10+x的效果
                if(flag=1) flag=0
                continue;
    if（j>0&&a[j-1]=10)                                           这里是个分支 选择将10+x的情形入栈保护 让后面的运算处理x就代表10 的情况
            push countA; push countB;push j-1;
    if(flag=0)                                                    计分部分的运算
            countA+=a[j];
            flag=1
    if(flag=1)
            countB+=a[j]
            flag=0
}
逆序 print  array[5][4] 不全为0的记录

[ 本帖最后由 zhu224039 于 2014-6-27 02:38 编辑 ]

递归思想：
令countA为f(a)
countB 为f(b)
令a[n]表示数据

f(a)=f(a-1)+a[i]   
f(b)=f(b-1)+a[j]
用这个公式形成递归
分析过程是不会变的，只是处理的方法变了   所以不重复分析过程了，直接写伪代码了

全局变量
array[5][4] a[n] countA countB
function(int countA,int coutB,int flag,int n，int i)
   for(j=n-1;j>=0;j--)
         if (countA==21 and  countB<=19) or （countA>21 and  countA-countB=2）
                       array[i][0]=countA;
                       array[i][1]=countB;                    保存猜解成功的结果
                       array[i][3]=j;                         保存猜解成功后的位置
                       array[i][4]+=1                        
                       return;
         if (countA=21 and countA-countB<-1)  or (countA>21 and ((countA-countB<-1) or (countA-countB>2))) 猜解失败什么事情都不干 返回
                       return;
         if(flag=0)                                进行计分 你计一次我计一次
            countA+=a[j];
            flag=1
         if(flag=1)                                 
            countB+=a[j]
            flag=0
          if（j>0&&a[j-1]=10)                       遇到x了
                function(countA,coutB,flag,j,i)       x就代表为10的情况
                if(flag=0) flag=1                                
                if(flag=1) flag=0                   制造连读的效果
                function(countA,coutB,flag,j,i)       x〉10的部分猜解
                                                                                先猜10的情况 再猜大于10的情况
}

void main()
{
      int i=0，flag=0;
  while  n>=0 {
      function(countA,coutB,flag,n，i)
      if(array[i][4]=1 )                                                  猜解成功 而且是只猜解成功一次
             n=array[i][3]                                                设置下次的 n值来调用函数
             i++；
      else
            print unknown                                                 其余情况就是猜解不成功了，当然程序也就结束了
            exit
   }
                                                                      对猜解进行判断  5局3胜制 猜解出的是4局胜利 错误
                                                                                               猜解出的是2局胜利 错误
    count=0                                                                                              1局胜利 错误  
                                                                                               天知道这个计分怎么捏造
    for(i=0;i<5;i++)                                                  
        if(array[i][4]=1)
            count++;
     if(count=3 or count=5)     
         逆序打印array里面的元素
     else
         print unknow
}

还是递归思路要清晰 好理解些  觉得最主要是程序负责了栈的处理，但是递归慢些

[ 本帖最后由 zhu224039 于 2014-6-27 04:42 编辑 ]

出于本人不会 文本操作   真正的代码就不写了

以后就这么干了  写程序之前 先用数学的方法进行抽象，用数学方法证明和推理，然后再来组织程序的结构部分
今天是happy的一天

[b][b][b][b][b][b][b]的啊

很高端的样子，学习了，

没有实现近似等于零