贪心算法流程图
活动安排问题//实现按结束时间从小到大排序,可用结构体存放,结构体包含开始时间,结束时间,序号#include <iostream>using namespace std;int c[1000];void select(int n,int a[],int b[],int c[]){c[1]=1;int j=1;for(int i=2;i<=n;i++){if(a[i]>=b
·
活动安排问题
//实现按结束时间从小到大排序,可用结构体存放,结构体包含开始时间,结束时间,序号
#include <iostream>
using namespace std;
int c[1000];
void select(int n,int a[],int b[],int c[]){
c[1]=1;
int j=1;
for(int i=2;i<=n;i++){
if(a[i]>=b[j]){
c[i]=1;
j=i;
}
else{
c[i]=0;
}
}
}
int main(){
int n;
cin>>n;
int a[n],b[n];
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
}
select(n,a,b,c);
for(int i=1;i<=n;i++){
if(c[i]==1)cout<<i<<endl;
}
}哈夫曼编码
//从文件中读取然后在输出到文件中,进行编码和译码
#include <iostream>
#include <fstream>
#include <cstring>
#include <math.h>
using namespace std;
#define n 100
#define m 2*n-1
typedef struct{
char ch;
char bits[9];
int len;
}CodeNode;
typedef CodeNode HuffmanCode[n + 1];
typedef struct{
int weight;
int lchild, rchild, parent;
}HTNode;
typedef HTNode HuffmanTree[m + 1];
int num;
char st[10000];
char get[10000];
void select(HuffmanTree HT, int k, int&s1, int&s2){
int i, j;
int minl = 32767;
for (i = 1; i <= k; i++){
if (HT[i].weight<minl&&HT[i].parent == 0){
j = i;
minl = HT[i].weight;
}
}
s1 = j;
minl = 32767;
for (i = 1; i <= k; i++){
if (HT[i].weight<minl&&HT[i].parent == 0 && i != s1){
j = i;
minl = HT[i].weight;
}
}
s2 = j;
}
int countAsc(char *s, int cnt[], char str[]){
char *p;
int i, j, k = 0;
int temp[257];
for (i = 0; i<257; i++){
temp[i] = 0;
}
for (p = s; *p != '\0'; p++){
temp[*p]++;
}
for (i = 0, j = 0; i <= 256; i++){
if (temp[i] != 0){
j++;
str[j] = i;
cnt[j] = temp[i];
}
}
num = j;
return j;
}
void createHuffmanTree(HuffmanTree& HT, HuffmanCode&HC, int cnt[], char str[]){
int i, s1, s2;
for (i = 1; i <= 2 * num - 1; i++){
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
HT[i].weight = 0;
}
for (i = 1; i <= num; i++){
HT[i].weight = cnt[i];
}
for (i = num + 1; i <= 2 * num - 1; i++){
select(HT, i - 1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
for (i = 1; i <= num; i++){
HC[i].ch = str[i];
}
}
void huffmanencoding(HuffmanTree &HT, HuffmanCode &HC){
int c, p, i;
char cd[n];
int start;
cd[num] = '\0';
for (i = 1; i <= num; i++){
start = num;
c = i;
while ((p = HT[c].parent)>0){
start--;
cd[start] = (HT[p].lchild == c) ? '0' : '1';
c = p;
}
strcpy(HC[i].bits, &cd[start]);
HC[i].len = num - start;
}
}
void decode(HuffmanCode &HC,char s[]){
char ch;
int num = 0;
ifstream in("CodeFile.txt");
string line;
char result[1000];
int z = 0;
if (in){
while (!in.eof()){
in >> ch;
result[z] = ch;
z++;
num++;
}
}
else{
cout << "没有此文件或读取错误!" << endl;
}
result[num-1] = '\0';
in.close();
char str[1000];
char cd[9];
int i, j, k = 0, p = 0, flag;
ofstream ou;
ou.open("TextFile.txt");
while (result[p] != '\0'){
flag = 0;
for (i = 0; i<num && flag == 0 && result[p] != '\0'; i++){
cd[i] = ' ';
cd[i + 1] = '\0';
cd[i] = result[p++];
for (j = 1; j <= num; j++){
if (strcmp(HC[j].bits, cd) == 0){
str[k] = HC[j].ch;
ou<<HC[j].ch;
k++;
flag = 1;
break;
}
}
}
}
ou.close();
str[k] = '\0';
strcpy(s, str);
}
void coding(HuffmanCode &HC, char str[], char get[]){
int i, j = 0;
while (str[j] != '\0'){
for (i = 1; i <= num; i++){
if (HC[i].ch == str[j]){
strcat(get, HC[i].bits);
break;
}
}
j++;
}
strcat(get,"\0");
int len =sizeof(get)/sizeof(get[0]);
}
void init(){
int i;
ifstream infile;
infile.open("ToBeTrain.txt");
i=0;
if(infile){
while(!infile.eof()){
infile>>st[i++];
}
}
i--;
i=0;
}
void dealwith(){
ofstream out;
out.open("CodeFile.txt");
out<<get;
out.close();
}
int main(){
char str[257];
int cn[257];
HuffmanTree HT;
HuffmanCode HC;
char sresult[10000];
get[0] ='\0';
int i;
char mn;
cout<<"输入0读取屏幕中的字符串,输入I对文件内容进行初始化，输入E对内容进行编码，输入D对内容进行解码."<<"请输入："<<endl;
cin>>mn;
while(mn!='Q'){
switch(mn){
case '0':
printf("please输入要编码的字符串:\n");
scanf("%s", &st);
num = countAsc(st, cn, str);
str[num + 1] = '\0';
createHuffmanTree(HT, HC, cn, str);
break;
case 'I':
init();
num = countAsc(st, cn, str);
str[num + 1] = '\0';
createHuffmanTree(HT, HC, cn, str);
break;
case 'E':
huffmanencoding(HT, HC);
printf("共有%d种符号\n", num);
for (int i = 1; i <= num; i++){
printf("字符%c次数为%d,编码为%s\n", HC[i].ch, cn[i], HC[i].bits);
}
coding(HC, st, get);
printf("哈夫曼编码为\n%s\n",get);
dealwith();
printf("编码后结果已存储在CodeFile.txt中\n");
break;
case 'D':
decode(HC, sresult);
printf("译码得：%s\n", sresult);
break;
}
cin>>mn;
}
}单源最短路径
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;// 正无穷
const int Maxsize=1e3+5;// 顶点数
int e[Maxsize][Maxsize];// 邻接矩阵
int book[Maxsize];// 标记
int dis[Maxsize];// 距离表
int n,m;// n:节点；m:边
int v1,v2,w;
int main()
{
scanf("%d%d",&n,&m);
// 初始化邻接矩阵
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)e[i][j]=0;
else e[i][j]=INF;
}
}
// input vex，arc
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v1,&v2,&w);
e[v1][v2]=w;
}
// init dis
for(int i=1;i<=n;i++)
{
dis[i]=e[1][i];
}
// init book
for(int i=1;i<=n;i++)book[i]=0;
book[1]=1;// 程序以源点为 1来举例
for(int i=1;i<=n-1;i++)// n-1次循环，而非n次循环(因为 1节点自身已确定)
{
// 找到距离1号顶点最近的顶点(min_index)
int min_num=INF;
int min_index=0;
for(int k=1;k<=n;k++)// n次循环
{
if(min_num>dis[k] && book[k]==0)
{
min_num=dis[k];
min_index=k;
}
}
book[min_index]=1;// 标记
for(int j=1;j<=n;j++)
{
// 节点 min__index =》j 有边
if(e[min_index][j]<INF)
{
// 加入之后使得距离变得更短
// 可以写为 dis[j]=min(dis[j],dis[min_index]+e[min_index][j]);
if(dis[j]>dis[min_index]+e[min_index][j])
{
dis[j]=dis[min_index]+e[min_index][j];
}
}
}
}
// print
for(int i=1;i<=n;i++)
{
printf("%d ",dis[i]);
}
puts("");// 换行
}prim算法
#include<cstdio>
#include<iostream>
using namespace std;
const int maxSize = 1000;
const int INF = 2147483647;
int n, m, G[maxSize][maxSize];
int d[maxSize];
bool vis[maxSize] = {false};
int prim(){
fill(d, d + maxSize, INF);
d[0] = 0;
int ans = 0;
for(int i = 0; i < n; i++){
int u = -1, min = INF;
for(int j = 0; j < n; j++){
if(vis[j] == false && d[j] < min){
u = j;
min = d[j];
}
}
if(u == -1) return -1;
vis[u] = true;
ans += d[u];
for(int v = 0; v < n; v++){
if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v]){
d[v] = G[u][v];
}
}
}
return ans;
}
int main(void){
int u, v, w;
cin>>n>>m;
fill(G[0], G[0] + maxSize * maxSize, INF);
for(int i = 0; i < m; i++){
cin>>u>>v>>w;
G[u][v] = G[v][u] = w;
}
int ans = prim();
cout<<ans<<endl;
for(int i = 0; i < n; ++i){
cout << d[i] << " ";
}
cout << endl;
}kruskal
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边
int fat[200010];//记录集体老大
struct node
{
int from,to,dis;//结构体储存边
}edge[200010];
bool cmp(const node &a,const node &b)//sort排序（当然你也可以快排）
{
return a.dis<b.dis;
}
int father(int x)//找集体老大，并查集的一部分
{
if(fat[x]!=x)
return father(fat[x]);
else return x;
}
void unionn(int x,int y)//加入团体，并查集的一部分
{
fat[father(y)]=father(x);
}
int main()
{
scanf("%d%d",&n,&m);//输入点数，边数
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息
}
for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化）
sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现）
for(int i=1;i<=m;i++)//从小到大遍历
{
if(k==n-1) break;//n个点需要n-1条边连接
if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体
{
unionn(edge[i].from,edge[i].to);//加入
tot+=edge[i].dis;//记录边权
k++;//已连接边数+1
}
}
printf("%d",tot);
return 0;
}删数问题
#include <iostream>
using namespace std;
int s[1000];
void del(int s[],int x,int y){
for(int j=x;j<y;j++){
s[j]=s[j+1];
}
}
int findmax(int s[],int l){
char max=s[0];
int t;
for(int i=1;i<=l;i++){
if(s[i]>max){
max=s[i];
t=i;
}
}
return t;
}
int main(){
int k;
int n;
string str;
cin>>str;
n=str.length();
for(int i=0;i<n;i++){
s[i]=str[i]-'0';
}
cin>>k;
int l=n;
int m=l-k;
int t,j;
for(int i=0;i<k;i++){
t=0;
j=0;
while(1){
if(s[j]>s[j+1]){
del(s,j,l);
l--;
t=1;
}
if(t==1)break;
if(j==l)break;
j++;
}
if(t==0){
int z=findmax(s,l);
del(s,z,l);
l--;
}
}
if(s[0]==0);
else cout<<s[0];
for(int i=1;i<m;i++){
cout<<s[i];
}
}
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)