程序员的算法趣题Q21--异或杨辉三角形

1. 问题描述

本题来自《程序员的算法趣题》中的第21题。

著名的杨辉三角形（帕斯卡三角形）的计算法则是“某个数值是其左上角的数和右上角的数之和”。这里用异或运算代替单纯的和运算，便得到所谓的“异或运算版杨辉三角形”。如下图所示：

图1 标准杨辉三角形和异或杨辉三角形

问题：在异或运算版杨辉三角形中，自上而下计算时，第2014个0会出现在哪一层。更一般地，第n(>0)个0会现在哪一层？

如上图所示，对比标准杨辉三角形和异或运算版杨辉三角形，可以发现，后者中的0/1与前者中的偶数/奇数是恰好对应的。因此这个问题相当于是问：在标准杨辉三角形中第n个偶数会出现在第几层？

2. 解法1—直观方法

直观的方法就是按照迭代的（iterative）方式从第1层开始从上而下计算每一层，计算过程中对0的个数以及层数(count from one)进行计数，当0的个数满足题设要求时即结束退出。

在每一层的计算中，要注意杨辉三角形的一个特征是每一个层的首尾两个数字都是1（不管是原始版还是异或运算版），这两个数字不需要也无法通过以上计算法则计算得出。

图2 实现方法1

当然，其中的cmp_flg并不是必须的。因为可以把结束判决条件放到for-loop外面，判决条件由（zeroCnt==2014）改为（zeroCnt>=2014）。

3. 解法2—利用比特运算

以上的直观方法不管是对于标准杨辉三角形中求偶数出现情况的问题还是异或运算杨辉三角中求0出现情况的都可行。但是，后者由于只要求异或运算，这就为利用bit-wise二进制操作运算特征来提高效率提供了可能性。

每一层的中间的数是由（在上一层中）它的左上的数和右上的数的异或运算而得。如果将每一层表达为一个整数（每个比特表示该层中的每一个数），则以上运算等价于是将上一层的数左移1比特后再与原数进行按比特异或运算而得，如下图所示：

图3 基于比特运算的计算例

当用于表示每一层的整数都初始化为0，且假定整数左移时右端补入0（各种编程语言中一般的缺省动作都是这样的），从以上运算示例可以看出，连两端的两个1也自然地被这样的计算所覆盖，因而不需要额外的初始化处理。

这里唯一需要注意的是，当计算的层数太多，所需要的比特数超过整型数表达范围的话，以上运算法则就行不通，需要进行数的拼接处理才能对应。在python3.x中支持超长整数的表达，所以不必担心这个问题。

4. 实现代码

以上两种实现方法的具体代码和测试代码如下所示：

# -*- coding: utf-8 -*-
"""
Created on Sat Aug  7 10:13:26 2021

@author: chenxy
"""

import sys
import time
import random
# from   typing import List

class Solution:
    def xor_yanghui1(self, N:int)->int:
        """
        :N:    Specify the serial-number of the zero to be searched
        :    
        :ret:  return the layer count
        """
        
        zeroCnt   = 0
        layerCnt  = 1
        prevLayer = [1]
        cmpFlg   = 0
        
        while(1):
            layerCnt += 1
            curLayer  = []  # Initialize the current layer to one empty list
            for k in range(len(prevLayer)-1):
                newData = (prevLayer[k]+prevLayer[k+1])%2
                curLayer.append(newData)
                if newData==0:
                    zeroCnt += 1
                    if zeroCnt == N:
                        # Because there are two layer of loop, we need an extra flag to indicate to
                        # exit from the outer layer of loop too.
                        cmpFlg = 1 
                        break
                
            if cmpFlg == 1:
                break
            else:
                # Update prevLayer for the computation of the next layer, by appending the two '1's 
                # in the head and tail.
                prevLayer = [1] + curLayer + [1]
        
        return layerCnt
    

    def xor_yanghui2(self, N:int)->int:
        """
        :N:    Specify the serial-number of zero to be searched
        :    
        :ret:  return the layer count
        """

        zeroCnt   = 0
        layerCnt  = 1
        prevLayer = 1
        
        while(1):
            layerCnt += 1
            curLayer = (prevLayer << 1) ^ prevLayer
            # Count the zero inside curLayer
            tmp = curLayer
            for k in range(layerCnt):                                
                zeroCnt += 1 - (tmp & 1) # Check whether the LSB is 0
                # print('layerCnt={0}, curLayer={1}, k={2}, tmp={3}, zeroCnt={4}'.format(layerCnt,curLayer,k,tmp,zeroCnt))
                tmp = tmp >> 1
            if zeroCnt >= N:
                break
            else:
                prevLayer = curLayer
        return layerCnt

    
if __name__ == '__main__':        
    
    sln = Solution()    
    
    N = 2014000
    t1 = time.monotonic()
    print('N = {0}, ans = {1}'.format(N, sln.xor_yanghui1(N)))
    t2 = time.monotonic()    
    print('N = {0}, ans = {1}'.format(N, sln.xor_yanghui2(N)))
    t3 = time.monotonic()    
    print('tCost1 = {0} sec, tCost2 = {1} sec'.format(t2-t1,t3-t2))

runfile('F:/CODEHUB/AlgorithmPuzzles/Q21-xor-yanghui.py', wdir='F:/CODEHUB/AlgorithmPuzzles')
N = 2014000, ans = 2094
N = 2014000, ans = 2094
tCost1 = 0.5150000001303852 sec, tCost2 = 0.39099999982863665 sec

在以上代码中，通过参数N指定所要搜索的0的序号，这样可以搜索任意某个序号的0所出现的行数。另外，从运行结果来看，两种实现方法的运行时间没有本质的差异，可能是因为其它周边处理（比如说搜索整数内含有0的个数的处理）的时间占据了主要的运算时间，掩盖了比特运算所带来的好处。

【2023-09-08】能否推导出以上问题的闭式表达式解呢？