2.已知维数求超立方体邻接矩阵

Myth丶恋晨 2022-06-02 09:58 200阅读 0赞

题目：n维超立方体是在n维空间中对三维空间立方体的类比，下图便是一个4维超立方体在三维空间中的投影及该立方体在三维空间的展开图

![四维超立方体及其展开图][E5_9B_9B_E7_BB_B4_E8_B6_85_E7_AB_8B_E6_96_B9_E4_BD_93_E5_8F_8A_E5_85_B6_E5_B1_95_E5_BC_80_E5_9B_BE.jpg]

给超立方体的各顶点编号后，就可以按照一定规则写出其邻接矩阵。请同学们根据下图寻找规律，对于给定的顶点编号序列，写出对应的超立方体的邻接矩阵。

![低维立方体示意图][E4_BD_8E_E7_BB_B4_E7_AB_8B_E6_96_B9_E4_BD_93_E7_A4_BA_E6_84_8F_E5_9B_BE.png]

输入：

维数n，顶点的编号序列a（0<=n<=7）

输出：

对应的超立方体的邻接矩阵（顶点顺序需与a一致）

<table style="width:1615px; margin-bottom:20px; background-color:transparent"> 
 <thead> 
  <tr> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> &nbsp;</th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 测试输入<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 期待的输出<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 时间限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 内存限制<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
   <th style="padding:4px; line-height:20px; vertical-align:bottom; border-top-width:0px"> 额外进程<span><a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助" style="vertical-align:text-bottom; border:0px; height:16px; padding-left:3px; width:16px"></a></span></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 测试用例 1</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=66664&amp;test=85742&amp;type=in&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">2↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">0&nbsp;1&nbsp;2&nbsp;3↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> <a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=66664&amp;test=85742&amp;type=out&amp;download=0" style="color:rgb(67,142,185); font-size:9pt" rel="nofollow">以文本方式显示</a> 
    <div style="vertical-align:top; padding:0px 5px 0px 0px; width:10em; height:10em; overflow:auto"> 
     <ol style="padding-left:0px; margin-bottom:0px; margin-left:2.5em; overflow:visible"> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">0&nbsp;1&nbsp;1&nbsp;0↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">1&nbsp;0&nbsp;0&nbsp;1↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">1&nbsp;0&nbsp;0&nbsp;1↵</span></li> 
      <li style="line-height:20px; font-family:Consolas,'Courier New',Courier,mono,serif; margin:0px; padding:0px; overflow:visible"> <span style="margin:0px; padding:0px; white-space:nowrap; background-color:rgb(211,211,211)">0&nbsp;1&nbsp;1&nbsp;0↵</span></li> 
     </ol> 
    </div> </td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 1秒</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 64M</td> 
   <td style="padding:4px; line-height:20px; vertical-align:middle; background-color:rgb(249,249,249)"> 0</td> 
  </tr> 
 </tbody> 
</table>

#include<stdio.h> 
    #include<math.h> 
    #include<string.h> 
    #include<map> 
    using namespace std; 
    int main() 
    { 
      //freopen("1.txt", "r", stdin); 
        int div; int adjec[128][128] = {0}; 
        int result[128][128] = { 0 }; 
      map<int, int> points; 
        scanf("%d", &div); 
     for (int i = 0; i <= div; i++)                //计算div+1次 
        { 
          int tmp = pow(2.0, i - 1);                //div-1维的矩阵边长 
            int p = 0; 
         for (int k = tmp; k < 2*tmp ; k++)        //两侧单位矩阵 
          { 
              adjec[p][k] = adjec[k][p] = 1; 
             p++; 
           } 
          for (int m = 0; m < tmp; m++)             //复制主对角矩阵 
         { 
              for (int n = 0; n < tmp; n++) 
               { 
                  adjec[m + tmp][n + tmp] = adjec[m][n]; 
             } 
          } 
           
       } 
      int num; int i = 0; 
        while (scanf("%d", &num) != EOF) 
       { 
          points.insert(pair<int, int>(num, i)); 
           i++; 
       } 
      int index = pow(2.0, div); 
     for (int i = 0; i < index - 1; i++) 
     { 
          for (int j = i+1; j < index; j++) 
           { 
              if (adjec[i][j]) 
               { 
                  int a = points.find(i)->second; int b = points.find(j)->second; 
                  result[a][b] = result[b][a] = 1; 
               } 
          } 
      } 
      for (int i = 0; i < index; i++) 
     { 
          for (int j = 0; j < index; j++) 
         { 
              if (j == index - 1) 
                    printf("%d\n", result[i][j]); 
              else 
                   printf("%d ", result[i][j]); 
           } 
      } 
     
     return 0; 
    } 
     
    /*#include<stdio.h>  
    #include<math.h>  
    #include<string.h>  
    int points[128]; 
    int adjec[130][130]; 
    int a1[2][2] = { 0, 1, 1, 0 }; 
    int main() 
    { 
        //freopen("1.txt", "r", stdin);  
       int div; 
       scanf("%d%*c", &div); 
      int point = pow(2.0, div); 
     int num; int all = 0; 
      while (scanf("%d", &num) != EOF) 
       { 
          points[all++] = num; 
       } 
      if (div == 0)            //0维时的情况  
     { 
          printf("0\n"); 
         return 0; 
      } 
      if (div == 1)            //1维时的情况  
     { 
          for (int i = 0; i < 2; i++) 
         { 
              for (int j = 0; j < 2; j++) 
             { 
                  if (j == 1) 
                        printf("%d\n", a1[i][j]); 
                  else 
                       printf("%d ", a1[i][j]); 
               } 
          } 
          return 0; 
      } 
      adjec[0][1] = 1; adjec[1][0] = 1;  //大于等于2维时的情况  
       for (int i = 2; i <= div; i++) 
      { 
          int tmp = (pow(2.0, i) / 2); 
           for (int m = 0; m < tmp; m++) 
           { 
              for (int n = 0; n < tmp; n++) 
               { 
                  adjec[m + tmp][n + tmp] = adjec[m][n]; 
             } 
          } 
          int p = 0; 
         for (int k = tmp; k < 2 * tmp; k++) 
         { 
              adjec[p][k] = adjec[k][p] = 1; 
             p++; 
           } 
      } 
      for (int i = 0; i < all; i++) 
       for (int j = 0; j < point; j++) 
     { 
          int tmp = points[i]; 
           if (j == point - 1) 
                printf("%d\n", adjec[tmp][j]); 
         else 
               printf("%d ", adjec[tmp][j]); 
      } 
      return 0; 
    }*/

[E5_9B_9B_E7_BB_B4_E8_B6_85_E7_AB_8B_E6_96_B9_E4_BD_93_E5_8F_8A_E5_85_B6_E5_B1_95_E5_BC_80_E5_9B_BE.jpg]: http://online.bit.edu.cn/moodle/pluginfile.php/166366/mod_programming/intro/%E5%9B%9B%E7%BB%B4%E8%B6%85%E7%AB%8B%E6%96%B9%E4%BD%93%E5%8F%8A%E5%85%B6%E5%B1%95%E5%BC%80%E5%9B%BE.jpg
[E4_BD_8E_E7_BB_B4_E7_AB_8B_E6_96_B9_E4_BD_93_E7_A4_BA_E6_84_8F_E5_9B_BE.png]: http://online.bit.edu.cn/moodle/pluginfile.php/166366/mod_programming/intro/%E4%BD%8E%E7%BB%B4%E7%AB%8B%E6%96%B9%E4%BD%93%E7%A4%BA%E6%84%8F%E5%9B%BE.png