计数问题（分治算法实现）

ゝ一纸荒年。 2023-07-17 06:17 9阅读 0赞

**题目：给定n个整数的数组A以及一个数x，设计一个分治算法，求出x在数组中出现的次数，并分析时间复杂度。**

# 算法思想： #

1.  先将问题划分为大小近似相等的两个字问题。
2.  对子问题递归调用该算法进行处理，递归出口为子问题只含一个元素，若该元素等于x,则返回x的出现次数为1，若该元素不等于x,则返回0
3.  原问题结果为这两个子问题所得结果之和。

核心代码：

int Countx(int arr[],int p,int r,int x){ 
    	int q;
    	if(p==r){ //p,r分别为子序列的左右边界下标，当两者相遇时（即子问题只有一个元素）递归出口
    	  if(arr[p]==x)//判断是否等于x,是则返回1
    		  return 1;
    	  else
    		  return 0;
    	}
    	else
    		q=(p+r)/2;//将问题不断划分为两子问题，直到子问题只有一个元素，递归结束
    	                //q为数组的中间位置
    		return(Countx(arr,p,q,x)+Countx(arr,q+1,r,x));//递归方程
    }

完整代码：

#include<stdio.h>
    int Countx(int arr[],int p,int r,int x){ 
    	int q;
    	if(p==r){ //p,r分别为子序列的左右边界下标，当两者相遇时（即子问题只有一个元素）递归出口
    	  if(arr[p]==x)//判断是否等于x,是则返回1
    		  return 1;
    	  else
    		  return 0;
    	}
    	else
    		q=(p+r)/2;//将问题不断划分为两子问题，直到子问题只有一个元素，递归结束
    	                //q为数组的中间位置
    		return(Countx(arr,p,q,x)+Countx(arr,q+1,r,x));//递归方程
    }
    
    int main(){ 
    	int arr[]={ 1,2,34,43,242,242,242,245};
    	int x,n;
    	printf("请输入待查找的数据!\n");
    	scanf("%d",&x);
    	n=Countx(arr,0,7,x);
    	if(n==0)
    		printf("查无此数据！\n");
    	else
    		printf("查到了！该数据在数组中的个数为%d\n",n);
    	return 0;
    }

*  时间复杂度分析:
 *  ![在这里插入图片描述][20200319230145491.png]
 *  利用公式法得：T(n)= O(n)
 *  烂尾：文章写到这基本烂尾了，可能大家都有一个这样的困惑，递归公式能否帮我们完成我们想要的结果，答案是肯定的。但是当我们带数据进去推理，大部分情况是一团晕，搞得对学习算法越来越没有信心，加油，那只是我们练的太少，多练肯定会懂得递归分治的套路，算法学习，切记眼高手低，还得多练，多去leedcode多刷题，加油！考虑到可能有些小伙伴，把递归和分治搞混淆！下面一个漫画也许能解开你的心结。
 *  [递归与分治][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]

[20200319230145491.png]: /images/20230528/da29bc7dd0524a5687e8eb9ae13abfd0.png
[Link 1]: https://www.sohu.com/a/334730105_298038
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYWh1YW5f_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/17bebf1b08fd473f90604d1f46e6e8eb.png