分治法习题

一.分治法设计一个算法，统计输入的非空字符串中给定字符的个数。

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 1000;
char str[maxn];
char TargetChar;
int CharNum;
int CountTargetCharNum(char s[], char TargetChar, int begin, int end)
{
    int L, R;
    if(begin == end) return (s[begin] == TargetChar);
    else
    {
        L = CountTargetCharNum(s, TargetChar, begin, begin + (end - begin)/2);
        R = CountTargetCharNum(s, TargetChar, begin + (end - begin)/2 + 1, end);
        return (L + R);
    }
}

int main()
{
    cout<<"Please enter a string:";
    gets(str);
    if(strlen(str) == 0)
    {
        cout<<"Don't allow to enter a NULL string!"<<endl;
        return 0;
    }
    cout<<"Please enter a char what you need to find:";
    cin>>TargetChar;
    CharNum = CountTargetCharNum(str, TargetChar, 0, maxn - 1);
    cout<<"Finding the char number:"<<CharNum<<endl;
    return 0;
}

二.非递归形式设计二分搜索程序。

int BinarySearch(int ArrayData[], int x, int n)
{
    int L = 0, R = n - 1;
    while(L <= R)
    {
        int mid = (L + R)/2;
        if(x == ArrayData[mid]) return mid;
        if(x > ArrayData[mid]) L = mid + 1;
        else R = mid - 1;
    }
    return -1; //未找到 x
}

三.16个硬币放袋子里，其中有一枚硬币是假币，并且那个伪造的硬币比真币轻，设计一个算法找到那枚假币。

#include <bits/stdc++.h>
#define ARRAY_SIZE 16
#define TRUE 1
#define FALSE 0
using namespace std;
int CallTimes = 0;
//生成包含 N 个硬币重量的数组(含一枚伪币)，并返回伪币位置
int GreateRandomCoinWeightArray(int *p, int N)
{
    int i, kt;
    int TrueCoinWeight, FakeCoinWeight;
    int IsStop;
    //生成随机数种子
    srand((unsigned)time(NULL));
    //生成随机真币重量值(在 50 ~ 100 之间)
    TrueCoinWeight = 50 + rand()%(100 - 50);
    //生成随机伪币位置(在 0 ~ N - 1 之间)
    kt = rand() % N;
    //设置真币重量
    for(i = 0; i < N; i++)
        if(i != kt)
            *(p + i) = TrueCoinWeight;
    //生成一个比真币略轻的伪币重量
    IsStop = FALSE;
    while(!IsStop)
    {
        FakeCoinWeight = 50 + rand()%(100 - 50);
        //
        if((TrueCoinWeight > FakeCoinWeight) && (TrueCoinWeight - FakeCoinWeight <= 5))
        {
            IsStop = TRUE;
            *(p + kt) = FakeCoinWeight;
        }
    }
    //返回伪币位置
    return kt;
}
//计算数组中硬币的重量和
int CalcCoinTotalWeight(int ArrayData[], int kb, int ke)
{
    int i, TotalWeight = 0;
    for(i = kb; i <= ke; i++) TotalWeight += ArrayData[i];
    return TotalWeight;
}
//采用分治法找到伪币(假定伪币一定存在且只有一枚)
//kb:(子)数组左边界( begin )
//ke:(子)数组右边界( end )
int FindFakeCoin(int ArrayData[], int kb, int ke)
{
    int LWeight, RWeight;
    CallTimes++;
    printf("<第 %d 次查找>
",CallTimes);
    if((ke - kb) == 1)  //(子)数组中仅包含两个元素
    {
        if(ArrayData[kb] < ArrayData[ke]) return kb;
        else return ke;
    }
    else //(子)数组中包含有多个元素
    {
        //计算子数组硬币重量
        LWeight = CalcCoinTotalWeight(ArrayData, kb, kb + (ke - kb)/2);  
        RWeight = CalcCoinTotalWeight(ArrayData,kb + (ke - kb)/2 + 1, ke);
        if(LWeight < RWeight)  //伪币在数组左半部分
            return FindFakeCoin(ArrayData, kb, kb + (ke - kb)/2);
        else      //伪币在数组右半部分
            return FindFakeCoin(ArrayData, kb + (ke - kb)/2 + 1, ke);
    }
}
int main()
{
    int ArrayData[ARRAY_SIZE];
    int i, k, FakeCoinPos;
    //生成包含 N 个硬币重量的数组(含一枚伪币),并返回伪币位置
    k = GreateRandomCoinWeightArray(ArrayData, ARRAY_SIZE);
    //输出随机数组内容
    printf("<生成的硬币重量数组值为(含一枚伪币)>:
");
    for(i = 0; i < ARRAY_SIZE; i++) printf("%d
",ArrayData[i]);
    printf("
");
    printf("<第 %d 枚为伪币>
",(k + 1));
    printf("
");
    //采用分治法找到伪币位置
    FakeCoinPos = FindFakeCoin(ArrayData, 0, ARRAY_SIZE - 1);
    printf("<找到第 %d 枚伪币>
",(FakeCoinPos+1));
    printf("
");
    //等待用户输入任意一键返回
    system("PAUSE");
    return 0;
}

四. 大于 1 的正整数 n，设计一个算法计算 n 有多少种不同的分解式。

int TotalModeNum = 0;
int CalcIntDecomModeNum(int n)
{
    if(n == 1) TotalModeNum++;
    else
    {
        for(int i = 2; i <= n; i++)
            if(n % i == 0)
                CalcIntDecomModeNum(n/i);
    }
}

五.给定 a, 分治法设计出 a^n 的算法

double CalcPow(double a, int n)
{
    if(n == 0) return 1.0;
    double b = CalcPow(a, n/2);
    b *= b;
    if(n%2==1) b *= a;   // 处理奇数次幂的情况
    return b;
}

六.给定两个长度相等的数组，分治算法求出合并后的排序数组的中位数。

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
const int maxn = 1000;
int a[maxn], b[maxn];
int CalcMedian(int a[], int n)
{
    if(n%2 == 0)
        return (a[n/2] + a[n/2-1])/2;
    else
        return a[n/2];
}

int CalcArrayMedian(int A[], int B[], int n)
{
    int m1, m2;
    if(n <= 0) return -1;
    if(n == 1) return (A[0] + B[0])/2;
    if(n == 2) return (max(A[0], B[0]) + min(A[1], B[1]))/2;

    m1 = CalcMedian(A, n);
    m2 = CalcMedian(B, n);

    if(m1 == m2) return m1;
    if(m1 < m2)
    {
        if(n%2 == 0) return CalcArrayMedian(A + n/2 - 1, B, n/2 + 1);
        else return CalcArrayMedian(A + n/2, B, n/2+1);
    }
    else
    {
        if(n%2 == 0) return CalcArrayMedian(B + n/2 - 1, A, n/2 + 1);
        else return CalcArrayMedian(B + n/2, A, n/2 + 1);
    }
}
int main()
{
    int m;
    cin>>m;
    for(int i = 0; i < m; i++) cin>>a[i];
    for(int i = 0; i < m; i++) cin>>b[i];
    int mid = CalcArrayMedian(a,b,m);
    cout<<mid<<endl;
    return 0;
}