PTA-2023第十一次练习题目
6-17 实验7_9_简单排序
法一:冒泡排序
上课学过好多好多次,讲解略过,代码有注释。
void bubbleSort(int data[],int elementCount)
{
for(int i = 0;i<elementCount-1;i++)//第一层循环,控制找最大值的次数
{
for(int j = 0;j<elementCount-1;j++)//第二层循环,每次找到一个最大值
{
if(data[j]>data[j+1]) //如果前一个数大于后一个数,就交换两个数
{
int x = data[j];
data[j] = data[j+1];
data[j+1] = x;
}
}
}
}
以下的几种排序方式,函数需要的接口与这道题提供的函数接口不相同,所以需要重新设置函数接口,这里不讲,我们只讲排序思路。
法二:快速排序(分治思想)
主体思路:定义一个数x属于数组s,利用双指针,将数组分为大于等于x和小于等于x的两部分,然后递归处理。(具体步骤如下)
1.
如上图所示,我们定义一个数组s用来储存n个数据,然后定义两个指针i j,分别指向数组的左右两端,同时i指针逐个向右移动扫描数组,j指针同理向左。
2.
当i,j指针扫描的过程中,当s[i]>x时,指针i就停止移动,同理当s[j]<x时,指针j就停止移动,然后交换s[i]与s[j],那么就使得大于x的s[i]去到了右边的数组,小于x的s[j]去到了左边的数组。
while(i<j)
{
do i++;while(s[i]<x);//i指针向右移动,当s[i]>x,移动停止,j同理
do j--;while(s[j]>x);
if(i<j)swap(s[i],s[j]);//如果i<j说明s[j]<x<s[i],就进行交换
}
3.
重复以上操作,直到i>=j为止。然后相同的方式利用递归处理左右两半边的数组,直到子数组长度等于1。
quick_sort(s,l,j);
quick_sort(s,j+1;r);
完整代码如下
int n;
int s[1000010];
void quick_sort(int s[], int l, int r)//将s[]数组的l-r区间内的数据排序
{
if (l >= r)return;
//以中点数据值作为分界值,避免边界问题。
//注意:以s[l],s[r]作为分界值时需要考虑边界问题,所以直接取中点値
int x = s[l + r >> 1], i = l - 1, j = r + 1;
while (i < j)
{
do i++; while (s[i] < x);//指针移动直到遇到不符合条件的值
do j--; while (s[j] > x);
if (i < j)swap(s[i], s[j]);//交换两值
}
quick_sort(s, l, j);//递归处理左右两边
quick_sort(s, j + 1, r);
}
法三:归并排序(分治思想)
主体思路:将数组均分为两半部分,分别有序化,然后合并两个数组
1.
将数组均分为两半部分,利用递归分别有序化。
int mid = l+r>>1;
merge_sort(s,l,mid);
merge_sort(s,mid+1,r);
2.
合并两个数组。利用两个指针i,j分别指向两个数组的起始位置,如果s[i]<s[j]就将s[i]放入新数组,反之放入s[j]。
int temp[1000010];//新数组
int k = 0,i = l,j = mid+1;//k负责控制新数组的下标
while(i<=mid&&j<=r)
{
if(s[i]<s[j]) temp[k++] = s[i++];
else temp[k++] = s[j++];
}
3.
因为我们上面使用的循环条件时while(i<=mid&&j<=r),所以当一个数组中的全部元素全部放入新数组时,另一个数组可能会还有剩余的数据,所以我们需要将这些数据也放入新数组中。
while(i<=mid) temp[k++] = s[i++];
while(l<=r) temp[k++] = s[j++];
4.
最后需要将新数组中的数据储存回原数组中,因为递归的过程中需要再次用到原数组,所以必须储存回去。
for(int i = l,j = 0;i<=r;i++,j++) s[i] = temp[j];//i控制原数组,j控制临时数组
完整代码如下:
int n;
int s[1000010];
void a(int s[], int l, int r)
{
if (l >= r)return;
int temp[1000010];
int mid = l + r >> 1;
a(s, l, mid);
a(s, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (s[i] < s[j])temp[k++] = s[i++];
else temp[k++] = s[j++];
}
while (i <= mid) temp[k++] = s[i++];
while (j <= r)temp[k++] = s[j++];
for (int i = l, j = 0; i <= r; i++, j++)
{
s[i] = temp[j];
}
}
法四:选择排序(对应题目6-21 实验7_13_选择排序)
选择排序算法描述如下:
从a[0]到a[n-1]这段元素中找最小元素a[min],a[0]和a[min]交换;接着,从a[1]到a[n -1]这段元素中找最小元素a[min],a[1]和a[min]交换;依次类推,直到从a[n-2]到a[n -1]这段元素中找最小元素a[min],a[n-2]和a[min]交换。
//函数功能:找数组中的最小值元素,并返回其下标
//参数说明:数组名,查找起始位置下标,查找终止位置下标
int findMin(int data[], int startLoc, int endLoc)
{
int minnum = startLoc;//用minnum表示最小值下标
for (int i = startLoc; i <= endLoc; i++)
{
if (data[i] < data[minnum]) minnum = i;//更新最小值
}
return minnum;
}
//输出数组中所有元素
//参数说明:数组,数组中已有元素个数
void outputData(int data[], int elementCount)
{
//注意格式
for (int i = 0; i < elementCount-1; i++)
{
printf("%d ", data[i]);
}
printf("%d\n", data[elementCount - 1]);
}
//选择排序(升序)
//参数说明:数组,数组中已有元素个数
void selectSort(int data[], int elementCount)
{
for (int i = 0; i < elementCount-1; i++)
{
int x = data[i];
//找到从a[i]到a[n -1]这段元素中找最小元素a[min]的下标
int num = findMin(data, i, elementCount - 1);
//交换当前值与最小值
data[i] =data[num];
data[num] = x;
//输出
outputData(data, elementCount);
}
}
法五:选择排序(对应题目6-19 实验7_12_插入排序)
将数组a的前n个元素按照升序的方式排序。
插入排序算法描述如下:
初始序列:49 38 65 97 76 13 27 49
将元素(38) 插入合适位置: [38 49] 65 97 76 13 27 49
将元素(65) 插入合适位置: [38 49 65] 97 76 13 27 49
将元素(97) 插入合适位置: [38 49 65 97] 76 13 27 49
将元素(76) 插入合适位置: [38 49 65 76 97] 13 27 49
将元素(13) 插入合适位置: [13 38 49 65 76 97] 27 49
将元素(27) 插入合适位置: [13 27 38 49 65 76 97] 49
将元素(49) 插入合适位置: [13 27 38 49 49 65 76 97]
void InsertSort(int a[], int n)
{
for (int i = 1; i < n; i++)//第一个数不需要排,从第二个数开始排
{
int temp =a[i];//将需要储存的数储存到temp中
for (int j = i-1; j>=0; j--)//从第i个数之前开始寻找tmep所在的位置
{
//如果说a[j]比temp大,那么temp所在的位置一定在a[j]之前,所以我们就将这个数后移一位
//从而在j之前为temp留出一个位置用来储存
if (a[j] > temp) a[j + 1] = a[j];
else//如果a[j]<=temp,那么temp就在a[j]的后一个位置
{
//将a[j+1]这个位置给temp用来储存
a[j + 1] = temp;
break;
}
//特殊判断0,否则就会数组越界
if (j == 0)
{
a[0] = temp;
}
}
for (int j = 0; j < n-1; j++)
{
printf("%d ", a[j]);
}
printf("%d\n", a[n - 1]);
}
}
6-18 实验7_10_发子弹
按照题目模拟就好(看注释)。
注意一个细节,题目中要求调整一直进行,直到子弹数相等为止。
但是当子弹数相等时,继续进行调整并不会改变数组中的子弹数,所以这个结束条件其实不需要考虑,直接进行num次即可,但是这时后复杂度就会提高,可能会超时。
但是这道题的测试数据比较水,并没有专门的考虑这个结束条件,所以直接写就好。
以下是不考虑以上细节的代码:
void distribute(int* bullets, int size, int number)
{
while (number--)//进行num次
{
int temp1 = 0, temp2;//用两个变量储存移动的子弹数
for (int i = 0; i < size; i++)//遍历一遍数组
{
//首先:如果是奇数,就++
if (bullets[i] % 2 != 0) bullets[i]++;
//将需要转移的子弹数储存到temp2
temp2 = bullets[i] / 2;
//然后储存剩余子弹数
bullets[i] /= 2;
//加上bullets[i-1]转移的子弹数temp1加到buttles[i]
bullets[i] += temp1;
//更新temp1
temp1 = temp2;
}
//最后,将buttles[size-1]转移的子弹数加到bettles[0]
bullets[0] += temp1;
}
}
6-20 实验7_11_循环移位
首先讲比较好想的一种方法
法一:
我构造一个循环是的序列每次推移一位,然后将该循环重复执行num次,就相当于是推移了num位
void shift(int* array, int num, int size)
{
int temp1 = 0, temp2;
while (num--)//循环num次
{
for (int i = size - 1, j = 0; j <= size; j++)//遍历一遍数组
{
//temp2储存当前的值,准备赋值到前一个位置
temp2 = array[i];
//将array[i+1]的值赋值给当前的array[i]
array[i] = temp1;
//更新temp1
temp1 = temp2;
//指针前移一位
i -= 1;
//如果指针超出边界,就推移到数组最后一位
if (i < 0)
{
i += size;
}
}
//注意j<=size使循环多了一次,使得最后一个数赋值给第一个循环的数。
}
}
法二:
第二种方式,就是直接推移num位。
因为只使用一个数组进行操作,需要考虑的特殊情况很多,所以我们直接使用两个数组
void shift(int* array, int num, int size)
{
int temp[100];//临时数组储存转换后的值
for (int i = 0; i < size; i++)
{
int j = i - num;//j 控制temp数组的小标
if (j < 0)//特殊判断j超边界
{
j += size;
}
//array[i]赋值到新位置temp[j]
temp[j] = array[i];
}
//将临时数组再赋值给原数组
for (int i = 0; i < size; i++)
{
array[i] = temp[i];
}
}
6-22 实验7_14_二分查找
直接讲整数二分,浮点数二分只需要修改细节就好(直接将两种模版,所有的二分都是这种模版)
1.
每次找到区间的中点,将s[mid]与x的值相比较。如果是图中的这种情况,x>s[mid] ,所以x存在于右区间。那么调整区间,将区间的左端点调整为mid+1(为什么是mid+1后面会讲),再去循环处理右区间。另一种情况同理。
2.
因为存在边界问题,所以这里的二分需要分情况讨论,对应的代码也有两种。
首先是边界调整的问题。重要的就是那边可以取到最后的值x,就将哪边的边界调整为mid。直接看代码讲。(代码题目是找到x在数组中的位置)
先看第一种:
int l = 0,r = n-1//设置左右端点
while(l<r)
{
int mid = l+r>>1;//设置中点
if(s[mid]<=x) r = mid;
//注意此时x可以在这个判断条件中取到,所以这个条件对应的边界调整为mid
else l = mid+1;
//另一个对应的调整为mid+1或mid-1;
}
第二种:
int l = 0,r = n-1;
while(l<r)
{
int mid = l+r+1>>1;
if(s[mid]<=x) l = mid;
//这时x可以在新的条件中取到,所以对应边界调整为mid,其余同理。
else r = mid-1;
}
3.
另外的,两种情况所移动的方向不同。
当用第一种模版时,将会从数组左向右去找x的值,直到从左向右找到第一个数为止,此时的边界l就是第一个x的位置。
当用第二种模版时,将会从右向左,直到找到一个数为止,l代表找到的第一个x的位置,注意使用这个模版时,mid = l+r+1>>1。
实验7_15_二分查找递归实现
二分递归实现,就是将上述的循环过程改为递归就好.
看代码:
int RecurBinarySearch(int a[], int x, int l, int r)
{
//不进行while循环
if (l >= r)//和while(l<r)的作用是一样的,如果l>=r就结束递归
{
if (a[l] == x) return l;//如果找到就返回下标
else return -1;//找不到就返回-1
}
int mid = l + r >> 1;
if (a[mid] >= x) return RecurBinarySearch(a, x,l, mid);//对右侧进行递归,边界的改变与正常代码相同
else return RecurBinarySearch(a, x,mid + 1, r);//同理
}
之前的博客"acwing week 1 总结" 对二分和排序有详细的讲解,有兴趣看一下。
12次题解周四晚发.
完结撒花!
标签:temp,49,第十一次,mid,PTA,int,while,数组,2023 From: https://www.cnblogs.com/csclixuan/p/17876783.html