c++寫的尋找一維陣列的重數和眾數,用分治法
1樓:王斌隨
其實用快排然後統計個數就可以了吧?當然,這個方法不是最佳的,但是是最容易想到的。
網上查詢的快排演算法:
快速排序。void quick_sort(int s, int l, int r)
s[i] = x;
quick_sort(s, l, i - 1); // 遞迴呼叫quick_sort(s, i + 1, r);}
大家幫幫忙,用遞迴演算法的分治策略求乙個陣列的眾數,用c語言編寫,告訴我演算法都可以!先謝
2樓:網友
眾數是最大值?
int maxeleposition(int a,int l,int r)
if(l < r)
int mid = l+r)/2;
int x = maxeleposition(a, l, mid);
int y = maxeleposition(a, mid+1, r);
if(a[x] >a[y])
return x;
else return y;
return l;
void main()
int aprintf("%d", maxeleposition(a, 0, 8));
查了一下,眾數是某個出現最多的數。那不要用上面的**了。
用分治法求陣列最大數(c語言)
3樓:匿名使用者
給,已經編譯運孫則雀行通過:
#include
#include盯含。
#define n 20
static long int tmp=1;
void getmax(int *a,int i,int j,int *fmax)
int mid,hmax,hmin,gmax,gmin;
tmp++;
if(tmp>則早=1000)
printf("the program mabye dead!");
exit(0);
if(i==j)
fmax=a[i]; return;
if(i==j-1)
if(a[i]>a[j])
fmax=a[i];return;elsefmax=a[j]; return;
elsemid=(i+j)/2;
getmax(a,i,mid,&gmax);
getmax(a,mid+1,j,&hmax);
fmax=gmax>hmax? gmax:hmax;
void main()
int max;
int a[n]=;
getmax(a,0,n-1,&max);
printf("max=%d",max);
分治法的適用條件?
4樓:墨汁諾
分治法的適用條件有以下四條,具體如下:
1、該問題的規模縮小到一定的程度就可以容易地解決。
2、該問題可以分解為若干個規模較小的相同問題,即該問題具有最優子結構性質。
3、利用該問題分解出的子問題的解可以合併為該問題的解;
4、該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子問題。
上述的第一條特徵是絕大多數問題都可以滿足的,因為問題的計算複雜性一般是隨著問題規模的增加而增加;第二條特徵是應用分治法的前提它也是大多數問題可以滿足的,此特徵反映了遞迴思想的應用。
分治策略。對於乙個規模為n的問題,若該問題可以容易地解決則直接解決,否則將其分解為k個規模較小的子問題,這些子問題互相獨立且與原問題形式相同,遞迴地解這些子問題,然後將各子問題的解合併得到原問題的解。這種演算法設計策略叫做分治法。
5樓:七夜_殤
分治法所能解決的問題一般具有以下幾個特徵:
1)該問題的規模縮小到一定的程度就可以容易地解決;
2)該問題可以分解為若干個規模較小的相同問題,即該問題具有最優子結構性質;
3)利用該問題分解出的子問題的解可以合併為該問題的解;
4)該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子子問題。
上述的第一條特徵是絕大多數問題都可以滿足的,因為問題的計算複雜性一般是隨著問題規模的增加而增加;第二條特徵是應用分治法的前提,它也是大多數問題可以滿足的,此特徵反映了遞迴思想的應用;第三條特徵是關鍵,能否利用分治法完全取決於問題是否具有第三條特徵,如果具備了第一條和第二條特徵,而不具備第三條特徵,則可以考慮貪心法或動態規劃法。第四條特徵涉及到分治法的效率,如果各子問題是不獨立的,則分治法要做許多不必要的工作,重複地解公共的子問題,此時雖然可用分治法,但一般用動態規劃法較好。
分治法的經典問題
6樓:人口政策
2)大整數乘法。
3)strassen矩陣乘法。
4)棋盤覆蓋。
5)合併排序。
6)快速排序。
7)線性時間選擇 (8)最接近點對問題(9)迴圈賽日程表。
10)漢諾塔。
1.分治法求解問題的一般步驟? 2.簡要說明什麼是動態規劃的最優子結構性質?急!
7樓:大人們
最優子結構:當問題的最優解包含了其子問題的最優解時,稱該問題具有最優子結構性質。
又被稱為最優化原理。
分解:將原問題分解為若干個規模較小將原問題分解為若干個規模較小,相互獨立,與原問題形式相同的子問題。
解決:若子問題規模較小而容易被解決則直接求解,否則遞迴地解各個子問題合併:將該層遞迴各個子問題的解合併為原問題。
vb問題。求用二分法求平方根。如何用二分法求平方根
option explicit private sub command1 click dim x s b x val s xb x s s do while abs s b s b 2 b x s s loops format s,print x 的立方根為 s end sub 你測試一下以上的 應...
用逐差法求加速度的公式是什麼,逐差法求加速度公式的推倒
來自楊三寨雪白的月季花 這兩種方法都對。從理論上來說,每種演算法的結果都是一樣的 實際上由於測量有誤差,所以要儘量利用更多的實驗資料,來消除偶然誤差,所以放棄左圖的方法一,而採用方法二 右圖中與左圖方法二的思路相同,最大限度地利用了速度與位移的測量值。只是經過計算變換以後,右圖代入的是位移值,不如左...
4和15用列舉法求最小公倍數,怎樣用列舉法求出最小公倍數
解 4的倍數有 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 15的倍數有 15 30 45 60 75 所以,4和15的最小公倍數是60 以上都錯了!我也不能為力呀!怎樣用列舉法求出最小公倍數 用列舉法找出最小公倍數,就是把每個數的倍數一一列舉出來,它...