算法设计与分析分治递归问题

Question

#include <stdio.h>
#include <stdlib.h>
void Zhong( int s[], int left,int right);
void Sort(int s[],int n);
int z=0 ;//众数
int c=0 ;//重数
int main()
{
int n,m,f;
FILE *fp=fopen("E:\\算法\\第2章分治策略实验包\\prog21众数问题\\test\\mode2.in","r");
if(fp==NULL)
{
printf("fp文件没有打开");
return 0;
}
fscanf(fp,"%d",&n);
printf("%d",n);
int s[n];
for(int i=0; i<n; i++)
{
fscanf(fp,"%d",&s[i]);
}
Sort(s,n);
printf("执行函数");
Zhong(s,0,n-1);
printf("执行完函数");
FILE *p=fopen("E:\\算法\\第2章分治策略实验包\\prog21众数问题\\answer\\mode2.out","r");
if(p==NULL)
{
printf("p文件没有打开");
return 0;
}
fscanf(p,"%d",&m);
fscanf(p,"%d",&f);
//printf("%d %d\n",m,f);
//printf("%d %d\n",z,c);
if(z==m&&c==f)
printf("YES");
else
printf("NO");
fclose(fp);
fclose(p);
return 0;
}
void Sort(int s[],int n)
{
int i,j,t;
for(i=0; i<n-1; i++)
{
for(j=i+1; j<n; j++)
{
if(s[i]>s[j])
{
t=s[i];
s[i]=s[j];
s[j]=t;
}
}
}
}
void Zhong( int s[], int left,int right)
{
// 找到中位数
int mid = s[(left + right) / 2];
// 与中位数相等的第一个数与最后一个数的位置
int left1 = 0, right1 = 0;
for (int i = left; i < right; i++)
{
if (s[i] == mid)
{
left1 = i;
break;
}
}
for (int i = left1; i < right; i++)
{
if (s[i] != mid)
{
right1 = i;
break;
}
}

if (c < right1 - left1 )
{
    c = right1 - left1 ;
    z = mid;
}

if (left1 > right1 - left1 )
{
    Zhong(s, left, left1);
}

if (right - right1  > right1 - left1 )
{
    Zhong(s, right1, right);
}

}
当mode2.in的内容为
50
6
3
7
1
11
3
15
3
10
3
12
5
14
7
1
8
5
6
13
11
3
14
7
7
5
10
14
12
12
4
14
10
5
11
1
15
11
3
12
3
12
15
5
5
11
14
4
3
11
9
时，mode2.out的内容为
3
8为什么程序不能正确执行，请用中文说明理由并改正这个程序

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题描述： 对于给定的一组数据，寻找其中出现次数最多的数，即众数。 程序对输入数据进行排序，然后再进行递归调用Zong函数来寻找众数。具体思路是：对于一个区间[left, right]，先找到中间位置mid，然后统计位于该区间中的数中与中位数相等的数的个数，如果这个个数超过区间长度的一半，即为所求的众数，否则说明众数位于[left, mid - 1]或者[mid + 1, right]中，于是递归调用该函数即可。 代码存在的问题：

1. 没有判断文件是否打开成功。
2. 数组的长度n应该是常量，而不是变量。因为在声明数组时需要固定数组大小。
3. 快速排序算法中出现了越界问题（注释里没有标注）。当右端点为n-1时，i和j可以取到n-2，下标n-1访问越界。
4. 函数Sort中的变量i、j、t声明时可以直接初始化： int i, j, t; 可以写成： int i = 0, j = 0, t = 0;
5. 在Zhong函数中，翻译中查找数字的起点应该是left1，而不是left。因为left是区间左端点的下标，left1是所查找数字的第一个位置的下标。
6. 在寻找与中位数相等的第一个数和最后一个数的位置时，若数列中没有与中位数相等的数，则right1的值仍为0，这样会导致程序无法正确执行。正确的做法应该是在查找第一个数后，当left1为0时，right1应该也设置为left1，即right1=left1，这样right1的值就不会为0。
7. 判断左侧区间时，递归调用Zhong函数的右端点应该为left1 - 1，而不是left1。
8. 判断右侧区间时，递归调用Zhong函数的左端点应该为right1，而不是right1 + 1。
9. 在比较统计中位数后，right1 - left1的值是否大于c时，c应该更新为right1 - left1，而不是原来的c加上right1 - left1。
10. 在比较左侧区间的长度和右侧区间的长度后，正确的做法应该是取两者中的较大值，然后递归调用相应的区间。因为左侧区间和右侧区间中可能都不包含众数，所以必须要对两者都进行递归调用。
11. 文件操作的模式应该为"w"而不是"r"，因为需要写入输出结果。 下面是修改后的程序：