排列问题、整数划分问题-程序员宅基地

1、排列问题：设r={r1,r2,…,rn}是n个元素的集合，求r的全排列。

（1）设计思想：

设 R={r1,r2,⋯,rn} 是要进行排列的n个元素。Rᵢ=R−rᵢ。集合X中元素的全排列记为 ᵢPerm(X)∘(rᵢ)Perm(X))表示在全排列Perm(X)的每个排列前加上前缀n ᵢrᵢ得到的排列。R的全排列可归纳定义如下：

当n=1时, Perm(R)=(r),其中r是集合R中唯一的元素;

当n>1时, Perm(R)由 (r1)Perm(R1),(r2)Perm(R2),⋯,(rn)Perm(Rn) 构成。

依此递归定义，可设计产生Perm(R)的递归算法如下：

（2）程序代码：

#include<stdio.h>
#include"iostream.h"
template <class Type>
void Perm(Type list[],int k,int m)
{
if(k==m)
{
for(int i=0;i<=m;i++)
cout<<list[i];
cout<<endl;
}
else
{
for(int i=k;i<=m;i++)
{
Swap(list[k],list[i]);
Perm(list,k+1,m);
Swap(list[k],list[i]);
}
}
}
template<class Type>
inline void Swap(Type &a,Type &b)
{
Type temp=a;
a=b;
b=temp;
}
void main()
{
int ar[]={1,2,3};
int n=sizeof(ar)/sizeof(ar[0]);
Perm(ar,0,n-1);
}

实验结果：

2、整数划分问题：将正整数n表示成一系列正整数之和，正整数n的这种表示称为正整数n的划分。求正整数n的不同划分的个数。例如：正整数6有11中不同的划分。

（1）设计思想：

在正整数n的所有划分中，将最大加数n₁不大于m的划分个数记作q(n，m)。可以建立q(n,m)的如下递归关系：

q(n,m)={1 q(n,n) 1+q(n,n−1) q(n,m−1)+q(n-m,m)}

n=1,m=1 n< m n=m n>m>1

据此,可设计计算q(n,m)的递归函数如下。正整数n的划分数p(n)=q(n,n)。

#include<iostream>

using namespace std;

int main()

{

int a,b,c;

int q(int n,int m);

cout<<"请输入整数及大于最大加数的数"<<endl;

cin>>a>>b;

c=q(a,b);

cout<<"所需要的划分数："<<c<<endl;

return 0;

}

int q(int n,int m)

{

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

if((n==1)||(m==1)) return 1;

if(n<m) return q(n,n);

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

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

}

实验结果

3、二分搜索技术：设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最大元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。

（1）设计思想：

时间完成搜索任务。二分搜索算法的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。如果x=a[n/2],则找到x,算法终止;如果x<a[n/2],则只在数组a的左半部继续搜索x；如果x>a[n/2]，则只在数组a的右半部继续搜索x。

（2）程序代码：

#include<iostream>
using namespace std;
int main()
{
int const length=100;
int n,x;
int a[length];
cout<<"依次输入数组的长度，数组内容、要查找的数"<<endl;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
cin>>x;
void BinarySearch(int a[],int n,int x);
BinarySearch(a,n,x);
return 0;
}
void BinarySearch(int a[],int n,int x)
{
int i,j,mid=0,left=0;
int right=n-1;
while(left<right+1&&left>=0)
{
int mid=(left+right)/2;
if(x==a[mid])
{
i=j=mid;
break;
}
if(x>a[mid])
left=mid+1;
else
right=mid-1;
}
if((i=j)&&(i>=0))
cout<<"所找数据在数组中下标为："<<i<<endl;
else
cout<<"所找数据不在数组中";
}

本文链接：https://blog.csdn.net/m0_65502432/article/details/137003909

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

E10/9/8/7:重写window.alert系统弹窗：文字过多自动换行，窗口右侧实现滑动精度条，倒计时弹窗确认关闭窗口-程序员宅基地

文章浏览阅读149次。E10/9/8/7重写window.alert系统弹窗：文字过多自动换行，窗口右侧实现滑动精度条，倒计时弹窗确认关闭窗口

Ansible批量部署zabbix-agent（含zabbix-agent的yum源，zabbix自动发现和添加的界面操作）_ansible 安装zabbix-agent-程序员宅基地

文章浏览阅读1.5k次，点赞4次，收藏19次。ansible 批量部署zabbix-agent，zabbix-server设置自动发现规则和自动添加主机，减轻咱们工作量_ansible 安装zabbix-agent

linux关于profile 、bashrc 、.bash_profile、.bashrc的区别_linux profile bashrc-程序员宅基地

文章浏览阅读1.4k次，点赞2次，收藏11次。linux关于profile 、bashrc 、.bash_profile、.bashrc的区别 - /etc/profile /etc/bashrc ~/.bash_profile ~/.bashrc 作用范围系统全局所有用户系统全局所有用户针对单个用户有效，如/home/user1/.bash_profile 中设定了环境变量，只针对 u_linux profile bashrc

springBoot源码之servlet与reactive_servlet和reactive-程序员宅基地

文章浏览阅读2.2k次，点赞3次，收藏5次。英语好的可以参考spring的官方文档：https://spring.io/reactiveReactive系统适合低延迟、高吞吐量的工作负载；Reactive Project和Spring结合，可以让开发人员搭建企业级的反应式系统，该系统是响应式的、弹性的、灵活的、消息驱动的。是Spring的reactive栈的非阻塞的基础,比如Spring WebFlux, Spring Data, 和 Spring Cloud Gateway。_servlet和reactive

svn【偷取此锁定】或【破除锁定】解锁SVN被锁定的文件的控制权-程序员宅基地

文章浏览阅读162次。现在很多项目开发都使用SVN作为馆控工具，SVN馆中的文件既可以以文件夹的方式获取，也可以通过eclipse导入。获取文件后，我们可以对某个文件锁定。如果某个同事锁定了某个文件，而他却找不到是在哪个地方（如工程或文件夹）锁定了该文件，则我们可以通过下面的方式获取该文件的控制权。偷锁然后再解锁操作SVN时中断锁定，文件的解锁方法1、右健选择svn -->获取锁定：..._svn偷锁

在Protel DXP中建造自己的原理图库-程序员宅基地

文章浏览阅读316次。Protel DXP是Altium公司的桌面板级电路设计系统，它集原理图设计输入、PCB设计绘制、模拟电路仿真、数字电路仿真、VHDL混合输入、FPGA设计、信号完整性分析等诸多功能于一体，是非常优秀的EDA软件．Protel DXP提供了丰富的元器件库，这些元器件库主要是集成库和PCB库．Protel DXP没有单独的原理图库，原理图符号存在于集成库中．即使这样，在使用的过程中，有时也经常遇到..._dxp 原理图生成元件库