笔试c基础题..docx

问题描述：八皇后问题是十九世纪著名数学家高斯于1850年提出的问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上问题分析 ：显然，每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1≤ i≤ n且1≤ xi≤ n，即第n个皇后放在第i行第xi列上由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:xi≠ xj;若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj;综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足的约束条件为:|i-xi|≠ |j-xj|回溯算法C非递归实现（可行则进,不行则换,换不成则退）----------------------------------------------------------------------------------------------#include#includeint x[100];bool place(int k)//考察皇后k放置在x[k]列是否发生冲突{    int i;    for(i=1;i=1)    {        x[k]=x[k]+1;   //在下一列放置第k个皇后        while(x[k]<=n&&!place(k))            x[k]=x[k]+1;//搜索下一列        if(x[k]<=n&&k==n)//得到一个输出        {            for(i=1;i<=n;i++)                printf("%d ",x[i]);            printf("\n");        //return;//若return则只求出其中一种解，若不return则可以继续回溯，求出全部的可能的解        }        else if(x[k]<=n&&k0)，每件物品价值为 V1，......VN (Vi>0)。

从这N件物品中选部分物品装入背包，使背包内物品的总重量不超过背包的容量TOTAL，并使背包中物品的总价值最高采用递归回溯求解）2.（多项式乘法）编写计算两个多项式相乘P(x)Q(x)=R(x)的函数： void muity(float a[],int m,float b[],int n,float c[]，int *k);其中数组a[],b[],c[]分别存放三个多项式的系数，m,n,k分别是多项式P(x)、Q(x)、R(x)的次数，通过形参与实参的结合返回c[],k的值3．（全部排列）给定n个不同的数字（n<10），利用递归方式编程求这n个数字的全部可能的排列要求包括:算法简介，源程序，对主要变量和重要语句的注释，运行结果的说明1------------------------------背包问题是一个非常有名的问题.可以这样叙述如下.假设有 n 件物品,记为 d1,d2,d3,…… dn.对于每一种物品di (1== v3/w3>= v4/w4>= v5/w5,这样算法再考虑将物品放入背包时,首先考虑的是取单价尽可能高的物品,以使背包的价值尽量大.在以后的程序 8.1 中,也遵循这样的惯例.程序 8.1 背包问题的类 knap 的定义及背包问题的解法typedef struct wvm {float weight; // 当前的重量float val; // 当前的价值int m; // 当前考察的物品件数.}WVM; // 解答空间树中的结点类型.#include #include using namespace std;template class knap {friend void knapsack( knap & );public:knap( const Typew total, const int num, Typep & value, Typew w1[ ], Typep v1[ ] );~knap( ){ delete [ ]w; delete []v;} private:Typep f( Typew remnant,int i ); // 从i+1 物品开始计算,背包的剩余重量 remnant// 可以达到的价值的最大上界.Typew TOT; // 背包的重量限制,如上例为 TOT 为37.int n; // 给定的物品件数,如上例为 n 为 5.Typew * w; // n 件物品的重量数组.Typep * v; // n 件物品的价值数组.Typep Y; // 得到的背包最优价值,初值为0.};template knap :: knap( const Typew total, const int num, Typep & value, Typew w1[ ], Typep v1[ ] ){TOT = total;n = num;Y = value;w = new Typew[n+1];v = new Typep[n+1];for (int j=1;j <= n; j++) { w[j]=w1[j];v[j]=v1[j];}}template Typep knap :: f( Typew t, int i ) {// remnant 背包的剩余重量.i 当前已经考察的物品件数. Typep amount = 0;++i;while( i <= n && w[i] <= t ) {t -= w[i];amount += v[i];++i;} // 按照物品的单价的递减序装填背包.if ( i <= n ) amount += t * v[i]/w[i];return amount;} // 得到背包的剩余重量所能够达到的最大的价值上界.template void knapsack( knap & ks ) { ks.Y = 0; // Y 记录在算法执行过程中得到一种填充方案时的背包价值,初值为0.stack s; // 记录当前重量,价值,已考虑的物品件数的堆栈WVM x; x.weight = 0.0; x.val = 0.0; x.m = 1; // 图9.16 所示根结点的右儿子s.push(x);x.weight = ks.w[1]; x.val = ks.v[1]; x.m = 1; // 图9.16 所示根结点的左儿子s.push(x);while ( s.empty() == false ) { x = s.top();if ( x.m == ks.n ) { if ( x.val > ks.Y ) ks.Y = x.val; // 当前一种填充方案的背包价值,可用// 作削减结点的价值约束.s.pop();}else if ( x.val + ks.f( ks.TOT - x.weight, x.m) > ks.Y ) { x.m += 1; //结点的右儿子的重量价值不变,考察物品的件数多了1件.s.pop( ); s.push(x); // 父结点弹出,其右儿子的各项数据进栈.if ( ( x.weight + ks.w[x.m]) <= ks.TOT ) // 若下一件物品重量和原背包重量之和小于重量// 限制 TOT, 则原结点的左儿子可生成.{ x.weight += ks.w[x.m]; //父结点的左儿子的重量.x.val += ks.v[x.m]; //父结点的左儿子的价值.s.push( x ); //左儿子的各项数据进栈.}}else s.pop( ); // 该结点不可能产生更好的结果,弹出.} cout << "The value of best knapsack filling solution is" << ks.Y << "!" << endl;}2-------------------------------------------*本程序在输入多项式时候，先输入低次系数，在输入高次*/ /*write by elva6401*/ #include int main() { int m,n,*k; int *a,*b,*c; int i; printf("Enter the number of m,n\n"); scanf("%d%d",&m,&n); m++; n++; a=(int *)malloc(m*sizeof(int)); b=(int *)malloc(n*sizeof(int)); c=(int *)malloc((m+n-1)*sizeof(int)); printf("Enter the a\n"); for(i=0;i