PAT：基础编程题目集-函数题6-9,6-10,6-11

69 阅读 0 评论 46 点赞

我是靠谱客的博主大力水壶，最近开发中收集的这篇文章主要介绍PAT：基础编程题目集-函数题6-9,6-10,6-11，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

6-9 统计个位数字

int Count_Digit ( const int N, const int D )//返回N中D出现的次数
{
if(N==0&&D==0)
return 1;
int ans[10]={0};
int m=abs(N);//取绝对值
int x;
while(m!=0)
{
x=m%10;
m=m/10;
ans[x]++;
}
return ans[D];
}

6-10 阶乘计算升级版

struct bigint
{
int buf[100];
int size;
//初始化
void init()
{
for(int i=0;i<100;i++)
buf[i]=0;
size=0;
}
//整数变大数
void set(int x)
{
init();
do
{
buf[size++]=x%10000;
x=x/10000;
}while(x!=0);
}
//大数乘法，重载*
bigint operator * (int
a) const
{
bigint ret;
ret.init();
int carry=0;//进位
for(int i=0;i<size;i++)
{
int tmp=buf[i]*a+carry;
ret.buf[ret.size++]=tmp%10000;
carry=tmp/10000;
}
if(carry!=0)
ret.buf[size++]=carry;
return ret;
}
//输出
void output()
{
for(int i=size-1;i>=0;i--)
{
if(i==size-1)
printf("%d",buf[i]);
else
printf("%04d",buf[i]);
}
printf("n");
}
}sum;
void Print_Factorial ( const int N )
{
if(N<0)
{
printf("Invalid input");
return;
}
//struct bigint sum;
sum.init();
sum.set(1);
for(int i=1;i<=N;i++)
sum=sum*i;
sum.output();
return;
}

编译有问题，可能是结构体放置的位置不对，可是不太懂怎么修改，难受，有人知道吗

6-11 求自定类型元素序列的中位数

快排解决

void quitsort(ElementType A[], int s,int t);
ElementType Median( ElementType A[], int N )
{
//快速排序
quitsort(A,0,N-1);
if(N%2==0)
return
A[N/2];
else
return
A[(N-1)/2];
}
void quitsort(ElementType A[], int s,int t)
{
int i=s,j=t;
ElementType tmp;
if(s<t)
{
tmp=A[s];
while(i!=j)
{
while(j>i&&A[j]>tmp)
j--;
A[i]=A[j];
while(j>i&&A[i]<tmp)
i++;
A[j]=A[i];
A[i]=tmp;
quitsort(A,s,i-1);
quitsort(A,i+1,t);
}
}
}

最后一个测试点过不了，可能到了快排最坏情况下：每次划分的基准都是最小的。复杂度O(n2)

归并排序：

#include<stdlib.h>
void merge(ElementType A[], int low,int mid,int high);//每一次二路归并,A[LOW]-A[mid-1]和A[mid]-A[high]
void mergepass(ElementType A[], int length, int n);//对整个表进行一趟归并
void mergesort(ElementType A[], int n);//从单个变两个，从两个变四个并，自底向上二路归并
ElementType Median( ElementType A[], int N )
{
//快速排序
mergesort(A,N);
if(N%2==0)
return
A[N/2];
else
return
A[(N-1)/2];
}
void merge(ElementType A[], int low,int mid,int high)
{
ElementType *r;
int i=low,j=mid+1,k=0;
//给r分配空间
r=(ElementType *)malloc((high-low+1)*sizeof(ElementType));
//序排序的两个集合里都还有元素
while(i<=mid&&j<=high)
{
//二路中较小的放入r
if(A[i]>A[j])
{
r[k]=A[j];
j++;k++;
}
else{
r[k]=A[i];
i++;k++;
}
}
//剩下的元素放入r
while(i<=mid)
{
r[k]=A[i];
i++;k++;
}
while(j<=high)
{
r[k]=A[j];
j++;k++;
}
//r复制进a中
for(k=0,i=low;i<=high;i++,k++)
{
A[i]=r[k];
}
free(r);
}
void mergepass(ElementType A[], int length, int n)
{
int i;
for(i=0;i+2*length-1<n;i+=2*length)
merge(A,i,i+length-1,i+2*length-1);
//处理两个数据数量不等的情况
if(i+length-1<n)
merge(A,i,i+length-1,n-1);
}
void mergesort(ElementType A[], int n)
{
int length;
for(length=1;length<n;length=2*length)
mergepass(A,length,n);
}

测试点全部通过，大N卡时21ms

~~其他的题目太简单了，不用写…~~