免费智能真题库 > 历年试卷 > 软件设计师 > 2019年上半年 软件设计师 下午试卷 案例
第4题      
知识点   数组   常量   基本思想   常量和变量

 
【说明】
n皇后问题描述为:在一个n×n的棋盘上摆放n个皇后,要求任意两个皇后不能冲突,即任意两个皇后不在同一行、同一列或者同一斜线上。
算法的基本思想如下:
将第i个皇后摆放在第i行,i从1开始,每个皇后都从第1列开始尝试。尝试时判断在该列摆放皇后是否与前面的皇后有冲突,如果没有冲突,则在该列摆放皇后,并考虑摆放下一个皇后;如果有冲突,则考虑下一列。如果该行没有合适的位置,回溯到上一个皇后,考虑在原来位置的下一个位置上继续尝试摆放皇后,……,直到找到所有合理摆放方案。
【C代码】
下面是算法的C语言实现。
(1)常量和变量说明
n: 皇后数,棋盘规模为n×n
queen[]:  皇后的摆放位置数组, queen[i]表示第i个皇后的位置, 1≤queen[i]≤n
(2)C程序
#include <stdio.h>
#define n 4
int queen[n+1];

void Show(){     /* 输出所有皇后摆放方案 */
         int i;
         printf("(");
         for(i=1;i<=n;i++){
                   printf(" %d",queen[i]);
          }
          printf(")\n");
}
int Place(int j){       /*  检查当前列能否放置皇后,不能放返回0,能放返回1 */
        int i;
        for(i=1;i<j;i++){    /*  检查与已摆放的皇后是否在同一列或者同一斜线上  */
               if(   (1)   )  ‖ abs(queen[i]-queen[j]) == (j-i))  {
                    return 0;
                }
        }
        return     (2)      ;
}
        void Nqueen(int j){
                 int i;
                 for(i=1;i<=n;i++){
                         queen[j] = i;
                         if(       (3)     ){
                               if(j == n) {      /* 如果所有皇后都摆放好,则输出当前摆放方案 */
                                       Show();
                               } else {          /* 否则继续摆放下一个皇后 */
                                               (4)    ;
                               }
                         }
                  }
}

int main(){
         Nqueen (1);
         return 0;
}


 
问题:4.1   (8分)
根据题干说明,填充C代码中的空(1)~(4)。
 
问题:4.2   (3分)
根据题干说明和C代码,算法采用的设计策略为 (5)。
 
问题:4.3   (4分)
当n=4时,有 (6) 种摆放方式,分别为 (7) 。
 
 
 



   知识点讲解    
   · 数组    · 常量    · 基本思想    · 常量和变量
 
       数组
               数组的定义及基本运算
               n维数组是一种"同构"的数据结构,其每个元素类型相同、结构一致。数组是定长线性表在维数上的扩张,即线性表中的元素又是一个线性表。
               数组结构的特点是:数据元素数目固定;数据元素具有相同的类型;数据元素的下标关系具有上下界的约束且下标有序。
               对数组进行的基本运算有以下两种。
               (1)给定一组下标,存取相应的数据元素。
               (2)给定一组下标,修改相应的数据元素中某个数据项的值。
               数组的顺序存储
               一旦定义了数组,结构中的数据元素个数和元素之间的关系就不再发生变动,因此数组适合于采用顺序存储结构。
               由于计算机的内存结构是一维线性的,因此存储多维数组时必须按照某种方式进行降维处理,即将数组元素排成一个线性序列,这就产生了次序约定问题。对二维数组有两种存储方式:一种是以列为主序的存储方式;另一种是以行为主序的存储方式。
               设每个数据元素占用L个单元,mn为数组的行数和列数,那么以行为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((i-1)n+(j-1))L
               同样的,以列为主序优先存储的地址计算公式为
               Loc(aij)=Loc(a11)+((j-1)m+(i-1))L
 
       常量
        与C语言不同,使用final关键字,C++语言则是const,如final float pi=3.14f、 final byte c=12。浮点常数后面要加"f",如12.7f、 1.02f。
 
       基本思想
        小波变换的基本思想是将信号展开成一族基函数的加权和,即用一族函数表示或逼近信号或函数。这一族函数是通过基本函数的平移和伸缩构成的。
        小波变换用于图像编码的基本思想就是把图像进行多分辨率分解,分解成不同空间、不同频率的子图像,然后再对子图像进行系数编码。小波变换本身并不具有压缩功能,之所以将它用于图像压缩,是因为生成的小波图像的能量主要集中于低频部分,水平、垂直和对角线上的高频部分则较少,可以将这一特性与一定的编码算法相结合,达到高效压缩图像的目的。小波变换作为一种多尺度、多分辨率的分析方法,由于小波具有很好的时频或空频局部特性,特别适合于按照人类视觉系统特性设计图像压缩编码方案,也非常有利于图像的分层传输。实验证明,图像的小波变换编码在压缩比和编码质量方面优于传统的DCT变换编码。
 
       常量和变量
        按照程序运行时数据的值能否改变,将程序中的数据分为常量和变量。程序中的数据对象可以具有左值和(或)右值,左值指存储单元(或地址、容器),右值是值(或内容)。变量具有左值和右值,在程序运行过程中其右值可以改变;常量只有右值,在程序运行过程中其右值不能改变。


 题号导航      2019年上半年 软件设计师 下午试卷 案例   本试卷我的完整做题情况 
1 /
2 /
3 /
4 /
5 /
6 /
 
↓第4题