由 洛谷 P5461 P1498 引发的杨辉三角形特性思考

本文主要是介绍由 洛谷 P5461 P1498 引发的杨辉三角形特性思考，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

源自洛谷 P5461 https://www.luogu.com.cn/problem/P5461

题目描述

现有 2ⁿ * 2ⁿ (n <= 10) 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。

给出 n，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。

输入格式

一个整数 n。

输出格式

 2ⁿ * 2ⁿ 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。

输入 

   3 

输出

0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1

这道题引发了我的一些思考，这道题固然可以递归做，不停的递归四个小正方形矩阵，并将左上角清零，直到无法再划分小正方形矩阵为之。

但是我们观察这个矩阵，我们可以惊讶的发现，这个矩阵的右半部分，正是杨辉三角的值%2的结果，于是我们可以有代码：

#include<iostream>
#include<cmath>
using namespace std;
int a[1050][1050];
int main()
{
    int n;
    cin >> n;
    n = 1 << n;
    a[0][n+1] = 1;
    for (int i = 1;i <= n;i ++)
    {
        for (int j = 1;j <= n;j ++)
        {
            a[i][j] = a[i-1][j]%2 + a[i-1][j+1]%2;
            cout << (a[i][j]%2) << ' ';
        }
        cout << endl;
    }
    
    return 0;
}

值得注意的是：

1. 1 << n 的含义为把1按二进制左移n位，即2的n次方

2. 当n较大时，会爆int，所以我们在状态转移的时候就把结果%2，最后输出答案的时候也%2，这样就不会爆int

3. 当然也可以把  a[i][j] = a[i-1][j]%2 + a[i-1][j+1]%2;  换成  a[i][j] = a[i-1][j] ^ a[i-1][j+1];  这样输出答案的时候就不用%2

4. ^ 为异或运算符，0 ^ 0 = 1, 1 ^ 1 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1

同样的有洛谷 P1498 南蛮图腾 ，此题也可以用杨辉三角形的 %2 特性做

https://www.luogu.com.cn/problem/P1498

题目描述

自从到了南蛮之地，孔明不仅把孟获收拾的服服帖帖，而且还发现了不少少数民族的智慧，他发现少数民族的图腾往往有着一种分形的效果，在得到了酋长的传授后，孔明掌握了不少绘图技术，但唯独不会画他们的图腾，于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙，作为一个好孙子的孙子的孙子的孙子……你能做到吗？

输入格式

每个数据一个数字，表示图腾的大小（此大小非彼大小） n<=10

输出格式

这个大小的图腾

输入#1

2

输出#1

   /\
  /__\
 /\  /\
/__\/__\

输入#2

3

输出#2

       /\
      /__\
     /\  /\
    /__\/__\
   /\      /\
  /__\    /__\
 /\  /\  /\  /\
/__\/__\/__\/__\

可以看出图腾有2的n次方行，而且带有一定的规律：

1. 当行数为奇数时，若对应数字为1，则输出 /\

2. 当行数为偶数时，若对应数字为1，则输出 /__\    并跳过下个数字继续循环

3. 当对应数字为0时，输出“  ”（即两个空格）

4. 每行的前导空格数量为 2ⁿ - i （i为行数）

对应的杨辉三角形%2如下图：

            1
           1 1 
          1 0 1 
         1 1 1 1 
        1 0 0 0 1 
       1 1 0 0 1 1 
      1 0 1 0 1 0 1 
     1 1 1 1 1 1 1 1 
    1 0 0 0 0 0 0 0 1 
   1 1 0 0 0 0 0 0 1 1 
  1 0 1 0 0 0 0 0 1 0 1
 1 1 1 1 0 0 0 0 1 1 1 1


则代码有：

#include<iostream>
using namespace std;
int f[1050][1050];
int main()
{
    int n;
    cin >> n;
    n = 1 << n;
    int t = n;
    f[0][n+1] = 1;
    for (int i = 1;i <= n;i ++)
    {
        for (int j = 1;j < t;j ++) cout << ' ';
        t --;
        for (int j = 1;j <= n;j ++)
        {
            f[i][j] = f[i-1][j]%2 + f[i-1][j+1]%2;
            f[i][j] %= 2;
        }
        bool flag = false;
        for (int j = 1;j <= n;j ++)
        {
            if (f[i][j] == 1) flag = true;
            if (f[i][j] == 1 || flag)
            {
                if ((i % 2 == 1) && f[i][j] == 1) cout << "/\\";
                if ((i % 2 == 0) && f[i][j] == 1)
                {
                    cout << "/__\\";
                    j ++;
                }
                if (!f[i][j]) cout << "  ";
            }
        }
        cout << endl;
    }
    return 0;
}

这篇关于由 洛谷 P5461 P1498 引发的杨辉三角形特性思考的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！