1、排列演算法
An?m=n(n?1)(n?2)....(n?m)
從n個數中挑選m個數進行排列，從第一個數開始，每個數可以從0到n個數中選擇,以此類推到第m個數，且前面用過的數后面就不能再用，故用mark[]去記錄這個數，并在每一次執行到m后清零，
#include <stdio.h>
#include <string.h>
#define N 5
#define M 3
int a[N];
int b[M];
int arrange (int x,int n,int m,int a[],int b[]){
static int mark[N] ={0};
if(x == m){
for(int i=0;i<m;i++){
printf("%d,",b[i]);
}
printf("\n");
return 0;
}
for(int i=0;i<n;i++){
if(mark[i] == 0){
b[x] = a[i];
mark[i] ++;
arrange(x+1,n,m,a,b);
mark[i] =0;
}
}
return 0;
}
int main(){
for(int i=0;i<N;i++)
a[i] = i+1;
return arrange(0,N,M,a,b);
}2、組合演算法
從n個數中選擇m個數進行組合排序，組合排序不允許有重復的物件，實作思路：
a、選擇數n，從剩下的n-1個數選擇m-1個數進行組合排序
b、選擇數n-1，從剩下的n-2個數選擇m-1個數進行組合排序
c、直到剩下m-1個數中選擇m-1個數進行組合排序
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define N 5
#define M 3
int a[5];
int b[3];
void combine (int n, int m,int a[],int b[])
{
printf("~~~~~~~~~%d,%d~~~~~~~\n",n,m);
for(int i= n;i>=m;i--)
{
b[m-1] =a[i-1];
if(m >1)
combine(i-1,m-1,a,b);
else{
for(int j=0;j< M;j++)
printf("%d ",b[j]);
printf("\n");
}
}
}
int main()
{
for(int i=0;i<5;i++)
a[i] = i;
combine(5,3,a,b);
}3、二分圖最大匹配演算法
二分圖的最大匹配的含義，就是說在A，B兩個集合中，A中的元素和B中的元素滿足某個條件即可連接起來，但每個點只能匹配一次，求最多可以有多少條連線即這個二分圖的最大匹配數，實作思路：
對集合A中每一個元素在去B中依次尋找滿足條件的連線，如果滿足條件的B中的元素未被占用，則標記該元素被占用，如果滿足條件的B中的這個元素已經被占用，那么就讓占用這個元素A集合中的元素去尋找新匹配元素，如果能找到則讓出該元素，不能找到則只能放棄該元素，
#include <stdio.h>
#include <string.h>
#define N 5
#define M 6
int a[N] = {2,4,5,9,3};
int b[M] = {1,5,6,9,4,11};
int ab[N];
int mark[M];
int pre[M] ;
int dfs (int x){
for(int i=0;i<M;i++){
if( (a[x] + b[i])% 3 == 0 && mark[i] ==0){
mark[i] = 1;
if( pre[i] == -1 || dfs(pre[i]) == 1 ){
pre[i] = x;
ab[x]= b[i];
return 1;
}
}
}
return 0;
}
int main(){
int count =0;
memset(pre,-1,sizeof(pre));
for(int i=0;i<N;i++){
memset(mark,0,sizeof(mark));
if(dfs(i) == 1) count++;
}
for(int i=0;i<N;i++)printf("i=%d,a=%d,ab=%d\n",i,a[i],ab[i]);
printf("count:%d\n",count);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259831.html
標籤：其他
上一篇：765. 情侶牽手