Tag:c/c++

Tag (c/c++)'s result:

6种排序算法效率比较

刚学C时写的程序,实现了冒泡,选择,插入,希尔,快速和归并排序,并对此6种排序算法进行了简单的效率比较。 #include <stdio.h> #include <stdlib.h> #include <time.h> #include <string.h> #include <windows.h> int str1[105],str2[105],str3[105],str4[105],str5[105]; int str1_1[105],str1_2[105],str1_3[105],str1_4[105],str1_5[105],str1_6[105]; int str2_1[105],str2_2[105],str2_3[105],str2_4[105],str2_5[105],str2_6[105]; int str3_1[105],str3_2[105],str3_3[105],str3_4[105],str3_5[105],str3_6[105]; int str4_1[105],str4_2[105],str4_3[105],str4_4[105],str4_5[105],str4_6[105]; int str5_1[105],str5_2[105],str5_3[105],str5_4[105],str5_5[105],str5_6[105]; int k,k1,k2,k3,k4,k5; int qcompare,qmov; int gcompare,gmov; int avbubblingc,avselectc,avinsertionc,avshellc,avquickc,avmergec; int avbubblingm,avselectm,avinsertionm,avshellm,avquickm,avmergem; void randint() //产生随机数数组 { int i,j; srand((unsigned)time(NULL)); for(i=0;i<100;i++) //模型数组 { str1[i]=rand()%101; str2[i]=rand()%101; str3[i]=rand()%101; str4[i]=rand()%101; str5[i]=rand()%101; } for(j=0;j<100;j++) { str1_1[j] = str1[j]; str1_2[j] = str1[j]; str1_3[j] = str1[j]; str1_4[j] = str1[j]; str1_5[j] = str1[j]; str1_6[j] = str1[j]; } for(j=0;j<100;j++) { str2_1[j] = str2[j]; str2_2[j] = str2[j]; str2_3[j] = str2[j]; str2_4[j] = str2[j]; str2_5[j] = str2[j]; str2_6[j] = str2[j]; } for(j=0;j<100;j++) { str3_1[j] = str3[j]; str3_2[j] = str3[j]; str3_3[j] = str3[j]; str3_4[j] = str3[j]; str3_5[j] = str3[j]; str3_6[j] = str3[j]; } for(j=0;j<100;j++) { str4_1[j] = str4[j]; str4_2[j] = str4[j]; str4_3[j] = str4[j]; str4_4[j] = str4[j]; str4_5[j] = str4[j]; str4_6[j] = str4[j]; } for(j=0;j<100;j++) { str5_1[j] = str5[j]; str5_2[j] = str5[j]; str5_3[j] = str5[j]; str5_4[j] = str5[j]; str5_5[j] = str5[j]; str5_6[j] = str5[j]; } } void printrand() //打印生成的随机数组 { int i; printf(“第一组\n”); for(i=0;i<100;i++) { printf(“%d “,str1[i]); } printf(“\n————————————\n”); printf(“第二组\n”); for(i=0;i<100;i++)……

hdu2015新生赛1008

这题wa了好多次,re了好多次,最后自己还是没有ac,仅放上wa代码记录本次的耻辱!(思路没问题,就是先把朋友推荐项目减完,再置0,如果钱<0就-1,=0就输出朋友推荐项目数,>0再玩剩下的项目,这时候对所有项目的钱进行小到大排序,一直减到小明的钱<0就输出count,我怀疑是快排那里出了问题,我是从1下标开始的……..) #include <stdio.h> #include <stdlib.h> int cmp(const void *p1,const void *p2) //比较函数 { return (*(int*)p1 – *(int*)p2); } int main() { __int64 t,i,j,u,m,n,count1; __int64 k; scanf(“%I64d”,&t); while (t–) { __int64 happymoney[10005]; //钱数组 int rcmd[10005] = {0}; //朋友推荐的项目 scanf(“%I64d%I64d%I64d”,&n,&m,&k); for (i=1; i<=n; i++) { scanf(“%I64d”,&happymoney[i]); //每个项目的钱 } for (j=1; j<=m; j++) { scanf(“%d”,&rcmd[j]); k = k – happymoney[rcmd[j]]; //小明的钱-朋友推荐项目的钱 happymoney[rcmd[j]] = 0; //朋友推荐项目的钱置0,方便后面排序 } if (k<0) printf(“-1\n”); //连朋友推荐项目都玩不完 else { if (k==0) printf(“%I64d\n”,m); //刚好玩光朋友推荐项目 else //剩下的钱还大于0 { qsort(happymoney,n,sizeof(happymoney[1]),cmp); //对非朋友推荐项目的钱小到大排序 count1 = m; for (u=m+1; u<=n; u++) //从第一个最少钱的非朋友推荐项目开始循环 { k = k – happymoney[u]; if (k<0) break; //玩不了这个项目,跳出循环 count1++; //这个项目可以玩 } printf(“%I64d\n”,count1); //打印可以玩的总项目数目 } } } return 0; } 仅供参考!

hdu1070

http://acm.hdu.edu.cn/showproblem.php?pid=1070 这题我用结构体,用cpe来存最便宜那个牛奶的数值(越小越便宜),再对结构体数组进行快排,可以ac。但是感觉有问题,当不同种类牛奶价格一样时,它们的容量都大于1000时,容量都会被赋值1000,那么这样如何再按相同便宜价格按容量大的输出呢?没搞懂,后面有我测的数据。 #include <stdio.h> #include <stdlib.h> struct milk { char milkname[105]; __int64 price; __int64 ml; double cpe; } mkind[105]; int cmps(const void*a,const void*b) { struct milk *x = (milk *)a; struct milk *y = (milk *)b; if (x->cpe!=y->cpe) return x->cpe – y->cpe; else return y->ml – x->ml; } int main() { int t,i,n; scanf(“%d”,&t); while (t–) { scanf(“%d”,&n); for (i=0; i<n; i++) { scanf(“%s%I64d%I64d”,mkind[i].milkname,&mkind[i].price,&mkind[i].ml); // getchar(); if (mkind[i].ml<200) mkind[i].cpe = 0x7f7f7f7f; else { if (mkind[i].ml>1000) mkind[i].ml = 1000; mkind[i].cpe = ((mkind[i].price * 1.0) / (mkind[i].ml / 200)); } } qsort(mkind,n,sizeof(mkind[0]),cmps); printf(“%s\n”,mkind[0].milkname); } return 0; } 这里我实验了3组数据,第一组应该输出uu吧,因为它容量最大 第二组没问题,第三组应该输出uio吧,不知道是我没理解题意还是杭电数据问题,不过可以ac………真奇怪。

hdu1061

http://acm.hdu.edu.cn/showproblem.php?pid=1061 这题我直接套快速幂取模的模板,见代码: #include <stdio.h> int qmod(__int64 a,__int64 b,__int64 c) { int ans = 1; a = a % c; while (b>0) { if (b&1) ans = (ans * a) % c; b = b>>1; a = (a * a) % c; } return ans; } int main() { __int64 n,t; scanf(“%I64d”,&n); while (n–) { scanf(“%I64d”,&t); printf(“%d\n”, qmod(t,t,10)); } return 0; }

hdu1021

http://acm.hdu.edu.cn/showproblem.php?pid=1021 这题注意防溢出,有两种方法解决,见代码: /*#include <stdio.h> //直接取余防溢出 __int64 fbnq[1000005]; int main() { int i,n; fbnq[0] = 7; fbnq[1] = 11; for(i=2;i<=1000002;i++) { fbnq[i] = ((fbnq[i-1] % 3) + (fbnq[i-2] % 3)) % 3; } while(scanf(“%d”,&n)!=EOF) { if(fbnq[n] % 3==0) printf(“yes\n”); else printf(“no\n”); } return 0; }*/ #include <stdio.h> //找规律,4个一组中第三个就是余数为0 int main() { __int64 n; while (scanf(“%I64d”,&n)!=EOF) { if (n % 4==2) printf(“yes\n”); else printf(“no\n”); } return 0; }

hdu2031—进制转换

http://acm.hdu.edu.cn/showproblem.php?pid=2031 此题我利用了STL的stack。 #include <iostream> #include <stack> //STL using namespace std; int main() { int a,b; while (cin>>a>>b) { int i; char j; stack<int> st; if (a<0) //若是负数,输出负号 { a=-a; cout<<“-“; } while (a!=0) { i=a%b; a=a/b; st.push(i); //入栈 } while (!st.empty()) //判空 { if (st.top()>9) { j=st.top()+55; cout<<j; //输出字母 } else cout<<st.top(); //输出栈顶元素 st.pop(); //移除栈顶元素 } cout<<endl; } return 0; }

hdu2068—RPG的错排

http://acm.hdu.edu.cn/showproblem.php?pid=2068 此题的思路是错排+排列组合 问题1:什么是错排? 答:十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题,是组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D(n)。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。 ———摘自《百度百科》问题2:如何推导错排公式? 答:递推推导错排公式: 当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用D(n)表示,那么D(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推. 第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法; 第二步,放编号为k的元素,这时有两种情况:⑴把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有D(n-2)种方法;⑵第k个元素不把它放到位置n,这时,对于这n-1个元素,有D(n-1)种方法; 综上得到 D(n) = (n-1) [D(n-2) + D(n-1)] 特殊地,D(1) = 0, D(2) = 1. —————–摘自《百度百科》问题3:这题该如何做? 答:关键点1.题目要求答对一半或以上的答案,那么利用错排,也就是错的答案在0~n/2之间,求出来再相加。 关键点2.比如5个女生,答错3个女生的名字,而这3个女生也有不同的组合,所以要用组合数乘错排数。 关键点3.当n为1时,答对是1,但是错排是0,所以要令sum(记录答对组数)初始值为1。附上ac代码: #include <stdio.h> __int64 comb(int n,int j) { int i,k; __int64 s = 1; __int64 x = 1; for (i=n; i>n-j; i–) s = s * i; for (k=1; k<=j; k++) x = x * k; return (s/x); } int main() { __int64 cp[30]; int i,j,n; while (scanf(“%d”,&n)&&n) { __int64 sum = 1; //注意初始为1(n=1是答对是1) cp[1] = 0; cp[2] = 1; for (i=3; i<=28; i++) cp[i] = (i-1) * (cp[i-1] + cp[i-2]); //错排公式 for (j=1; j<=n/2; j++) sum = sum + (cp[j] * comb(n,j)); printf(“%I64d\n”,sum); } return 0; }

Circular links

循环链表是使最后一个结点的next指针指向表头结点,构成循环,这里我只实现了循环链表的创建和打印操作。 #include <stdio.h> #include <malloc.h> typedef struct lnode { int data; struct lnode *next; } LNODE,*linklist; //打印链表元素 void print_list(linklist L) { linklist p; printf(“建立的循环链表为:\n”); p = L->next; //指向结点(非头结点) while (p!=L) { printf(“%d “,p->data); p=p->next; } printf(“\n”); } //创建循环链表 void creat_list(linklist L) { linklist p,q; L->next = L; //指向自己 printf(“请输入链表元素:\n”); q = (linklist)malloc(sizeof(LNODE)); scanf(“%d”,&(q->data)); q->next = L->next; //q的后指针指向头结点 L->next = q; //头结点的后指针指向新开的q p = (linklist)malloc(sizeof(LNODE)); while ((scanf(“%d”,&(p->data)))!=EOF) { p->next = q->next; //新开的p的后指针指向前一个q的后指针 q->next = p; //q的后指针指向新开的p q = p; //q记录 p=(linklist)malloc(sizeof(LNODE)); //p再新开 } } int main() { linklist L; //是地址 L = (linklist)malloc(sizeof(LNODE)); creat_list(L); print_list(L); return 0; }

Two-way linked-list

双向链表在链表的基础上新增了指向前一个结点的指针prior, 由于链表没设表长属性,我在程序用了count变量记录表长以方便插入操作。这里我实现的是双向链表的创建,打印,插入和删除操作。 #include <stdio.h> 2 #include <malloc.h> 3 4 typedef struct shuang 5 { 6 struct shuang *prior; //指向前一个结点 7 int data; 8 struct shuang *next; //指向后一个结点 9 } snode, *slinklist; 10 11 //打印双向链表元素 12 void print_shuang(slinklist L) 13 { 14 slinklist p; 15 p = L->next; 16 while (p!=NULL) 17 { 18 printf(“%d “,p->data); 19 p = p->next; 20 } 21 printf(“\n”); 22 } 23 24 //创建双向链表 25 void creat_shuang(slinklist L) //得结点地址 26 { 27 slinklist p,q; 28 L->next = NULL; //头结点的后指针先指向null 29 printf(“请输入链表元素\n”); 30 q = (snode *)malloc(sizeof(snode)); 31 scanf(“%d”,&(q->data)); 32 q->next = L->next; //NULL给了q->next 33 L->next = q; //L(头结点)指向新的q 34 q->prior = L; //新的q的前指针指向前一个L 35 p = (snode *)malloc(sizeof(snode)); 36 while (scanf(“%d”,&(p->data))!=EOF) 37 { 38 p->next = q->next; //p的后指针指向q的后指针 39 q->next = p; //q的后指针改为指向新的p 40 p->prior = q; //新的p的前指针指向上一个q 41 q = p; //上一个q变成这次新的p(q记录p) 42 p = (snode *)malloc(sizeof(snode)); //p再新开 43 } 44 } 45 46 //插入 47 int ins(slinklist L,int i,int e) 48 { 49 slinklist p,q,s; 50 int j = 1; 51 int count =……

LinkedList

链表的结点中有指针域,这里先写最初级的链表(后续会有链表的进化型和究极进化型) 几个关键点: 1.头指针 2.插入和删除操作的指针修改 3.插入和删除操作的各种情况分析(具体的看注释) 4.记录指针 下面以一个学生成绩管理程序为例: #include <stdio.h> #include <malloc.h> #define NULL 0 struct student { int num; //学号 double score; //分数 struct student *next; //指向下一个学生 }; int main() { struct student *del(struct student *head,int num); //删除声明 struct student *ins(struct student *head,struct student *stu); //插入声明 int n = 0; int dnum; struct student *head,*p,*p1,*p2,*p3,stu; head = NULL; //先让头结点指针为空 p1 = (struct student*)malloc(sizeof(struct student)); //开辟空间 scanf(“%d%lf”,&p1->num,&p1->score); do { n = n+1; if (n==1)head = p1; //若是第一个结点,就给head else p2->next = p1; //非第一个结点,就给p2的下一个结点 p2 = p1; //把p1先给p2 p1 = (struct student*)malloc(sizeof(struct student)); //p1再新开一个内存区 scanf(“%d%lf”,&p1->num,&p1->score); } while (p1->num!=0); //号数输入为0就结束了 p2->next = NULL; //最后一个结点的next指向null没了 p = head; //创建链表完毕————————————– while (p!=NULL) { printf(“%d\t%lf\n”,p->num,p->score); p = p->next; //指针后移输出结点信息 } printf(“请输入需要删除的学号:”); scanf(“%d”,&dnum); p = del(head,dnum); //返回删除后的头结点,删除完毕—————————— p3 = p; //记录删除后的链表! while (p!=NULL) { printf(“%d\t%lf\n”,p->num,p->score); p = p->next; } printf(“请输入需要增添的学号及其数据”); scanf(“%d%lf”,&stu.num,&stu.score); p = ins(p3,&stu); //返回插入后的头结点,插入完毕——————————- while (p!=NULL) { printf(“%d\t%lf\n”,p->num,p->score); p = p->next; } return 0; } struct student *del(struct student *head,int num) //传头结点与要删除的号数进来 { struct student *p1,*p2; if (head==NULL) { printf(“NO\n”); } p1 = head; while (num!=p1->num&&p1->next!=NULL) //要删除的号数不是第一个并且没到或等于最后一个……