看到大一数据结构作业~突然感觉最近犯困~思考跟不上了~~有没有高手能帮忙讲解或实现一下~~

看看我理解对不对~

第一题~

冒泡排序交换次数就是逆序对个数~
同理可得~归并排序数据变动次数以及排序数组长度可以推测逆序对个数~

[此贴子已经被作者于2017-5-26 18:33编辑过]

还看看我理解对不对~

第二题~

合并先从最短的数列开始合并~合并后长度为原来长度的总和~

感觉和哈夫曼树从底到顶选取最低频率的两个作为子树合并的构建方法类似~~

[此贴子已经被作者于2017-5-26 10:48编辑过]

感觉构建哈夫曼树用小顶堆构建效率较高~~看来有时间还要看看堆那一块才行~

找到了参考源码~可以参考一下~

这个是用分治法求逆序数的~

#include<stdio.h>
#include<cstdio>
#include<cstring>


int n;
int a[20];
int cnt;

void query(int a[], int first, int mid, int last, int tmp[]){
    int i = first, j = mid+1;
    int k = 0;
    while(i <= mid && j <= last){
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else{
            tmp[k++] = a[j++];
            cnt += mid-i+1;
        }
    }
    while(i <= mid){
        tmp[k++] = a[i++];
    }
    while(j <= last){
        tmp[k++] = a[j++];
    }
    for(int id = 0; id < k; id++){
        a[first + id] = tmp[id];
    }
}

 
void merge_sort(int* a, int L, int R, int* tmp){
    if(L < R){
        int M = L + (R-L)/2;
        merge_sort(a,L,M,tmp);
        merge_sort(a,M+1,R,tmp);
        query(a,L,M,R,tmp);
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
    }
    int tmp[20];
    cnt = 0;
    merge_sort(a,0,n-1,tmp);
    for( i = 0; i < n; i++){
        printf("%d ",a[i]);
    }
    printf("cnt = %d\n",cnt);
    printf("\n");
    return 0;
}

这个是关于贪心算法求合并数列解的~

#include<stdio.h>
#include<stdlib.h>
int getMin(int[],int);//求最优合并算法比较次数
int getMax(int[],int);//求最差合并算法比较次数
void quick_sort(int*,int,int);//快速排序，用来对各序列根据序列长度按从小到大排序
int main()
{
    int data[100],n,i,min,max;
    printf("请输入待合并的序列总个数K:\n");
    scanf("%d",&n);
    printf("请依次输入这些序列中的元素个数：\n");
    for(i=1;i<=n;i++)
    scanf("%d",&data[i]);
    quick_sort(data,1,n);
    max = getMax(data,n);
    min = getMin(data,n);
    printf("1.最优合并算法的比较次数为：%d\n2.最差合并算法的比较次数为 %d\n",min,max);
    system("pause");

 return 0;
}
int getMin(int data[100],int n)
{
    int sum=0,i;
    if(n==1) return data[n];
    for(i=1;i<n;i++)
    {
        sum+=data[i]+data[i+1]-1;
        data[i+1]=data[i]+data[i+1];
        quick_sort(data,i+1,n);
    }
    return sum;


}
int getMax(int data[],int n)
{

 int i,sum=0,amount;//sum记录当前比较次数的总和，amount当前最大序列的长度
 amount = data[n];

 if(n==1) return amount;

 for(i=n-1;i>=1;i--)

 {
  sum += amount+data[i]-1;//当前最大两个序列合并需要的比较次数
  amount +=data[i];//合并两个序列后，当前最大序列的长度
 }

 return sum;
}

void quick_sort(int s[], int l, int r)
{
    if(l<r)
    {
        int i=l, j=r, x=s[l];//取第一个做数做基准，用x表示
        while(i<j)
        {
            while(i<j && s[j]>= x) // 从右向左找第一个小于x的数
                j--;
            if(i<j)
                s[i++]=s[j];

            while(i<j && s[i]< x) // 从左向右找第一个大于等于x的数
                i++;
            if(i<j)
                s[j--]=s[i];
        }
        s[i] = x;
        quick_sort(s, l, i-1); // 递归调用
        quick_sort(s, i+1, r);
    }
}

如把3/7和13/23分别化为三个单位分数的和

【贪心算法】

设a、b为互质正整数，a<b 分数a/b 可用以下的步骤分解成若干个单位分数之和：

步骤一： 用b 除以a，得商数q1 及余数r1。（r1=b - a*q1）

步骤二：把a/b 记作：a/b=1/(q1+1）+(a-r1)/b(q1+1）

步骤三：重复步骤2，直到分解完毕

3/7=1/3+2/21=1/3+1/11+1/231

13/23=1/2+3/46=1/2+1/16+1/368

以上其实是数学家斐波那契提出的一种求解埃及分数的贪心算法，准确的算法表述应该是这样的：

设某个真分数的分子为a，分母为b;

把b除以a的商部分加1后的值作为埃及分数的某一个分母c；

将a乘以c再减去b，作为新的a；

将b乘以c，得到新的b；

如果a大于1且能整除b，则最后一个分母为b/a；算法结束；

或者，如果a等于1，则，最后一个分母为b；算法结束；

否则重复上面的步骤。

备注：事实上，后面判断a是否大于1和a是否等于1的两个判断可以合在一起，及判断b%a是否等于0，最后一个分母为b/a，显然是正确的。


这有一个贪心算法的例子 不过我没看的太懂

我也表示数学这块没怎么消化~到底现在我还是高数渣渣~

表示我们数学没将这块。