介绍2题 整数划分和递归算法!

实验 递归与分治策略

一、 实验目的

1、 掌握递归的概念和递归函数的设计方法；

2、 掌握分治的思想和用分治法解决实际问题。

二、 实验内容

1、 整数划分问题

问题描述：将正整数n表示成一系列正整数的和，即

n＝n1+n2+…+nk（其中n1>=n2>=…>=nk，nk>=1）

正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记作p（n）。

设计程序实现求正整数n的划分数。

程序实现:

#include<iostream.h>

#include<conio.h>

#include <iomanip.h>

int q(int n,int m)//求对整数n不大于m的划分数

{

if((n<1)||(m<1)) return 0;

if

if

if

return q(n,m-1)+q(n-m,m);

}

void main()

{

int N,M;

char flg;

do{

cout<<"请输入你要划分的正整数N和最大的加数M" <<endl;

cin >>N;

cin>>M;

cout<<"对正整数: "<<N<<" 不大于 "<<M<<"的最大划分数有："<<endl; cout<<q(N,M)<<" 个"<<endl;

cout<<"是否继续输入(Y/y)？按其它任意键退出";

cin>>flg;

}while(flg == 'Y' ||flg == 'y');

}

算法验证：请通过适当的测试用例来测试以上程序的正确性。

例如正整数6不大于6的划分有11种，即q（6，6）＝11。正整数7不大于7的划分有15

介绍2题 整数划分和递归算法!

种，即q（7，7）＝15。

并说明为什么选用这些测试用例。

2、 棋盘覆盖问题

问题描述：

在一个2k×2k 个方格组成的棋盘（如图1-1）中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌（如图1-2）覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

图1-1 棋盘

#include<iostream.h>

#include<conio.h>

#include <iomanip.h>

#include<stdio.h>

#define BOARD_SIZE 4

int Board[BOARD_SIZE][BOARD_SIZE];

void ChessBoard(int tr,int tc,int dr,int dc,int size)

{

static int tile=1;

if(size==1) return;

int t = tile++,

s = size/2;

if(dr<tr+s && dc< tc+s)

ChessBoard(tr,tc,dr,dc,s);

else{

Board[tr+s-1][tc+s-1]=t;

ChessBoard(tr,tc,tr+s-1,tc+s-1,s);

}

if(dr<tr+s && dc>=tc+s)

ChessBoard(tr,tc+s,dr,dc,s);

else{

Board[tr+s-1][tc+s]=t;

ChessBoard(tr,tc+s,tr+s-1,tc+s,s);

}

图1-2 四种不同的L型骨牌

介绍2题 整数划分和递归算法!

if(dr>=tr+s&&dc<tc+s)

ChessBoard(tr+s,tc,dr,dc,s); else{

Board[tr+s][tc+s-1]=t;

ChessBoard(tr+s,tc,tr+s,tc+s-1,s); }

if(dr>=tr+s&&dc>=tc+s)

ChessBoard(tr+s,tc+s,dr,dc,s); else{

Board[tr+s][tc+s]=t;

ChessBoard(tr+s,tc+s,tr+s,tc+s,s); }

}

void main()

{

int i,j;

Board[2][2]=0;

ChessBoard(0,0,2,2,BOARD_SIZE); for(i=0;i<BOARD_SIZE;i++) {

for(j=0;j<BOARD_SIZE;j++) {

printf("%-4d",Board[i][j]); }

printf("\n");

}

}

------------------------Mr.sheng