算法设计与分析-上机实验5

P124 4.9练习题
3.已知有序表为{3, 5, 7, 8, 11, 15, 22, 23, 27, 29, 33}，求用二分查找法查找27时所需的比较序列和比较次数

// By SnowDream
#include <iostream>
#include <vector>
using namespace std;

int compareCount = 0; // 记录比较次数

// 打印当前正在比较的子序列
void printSubVector(const vector<int>& a, int low, int high) {
    cout << "当前比较序列: ";
    for (int i = low; i <= high; ++i) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int binsearch(vector<int>& a, int low, int high, int k) { // 二分查找递归算法
    if (low <= high) { // 当前区间存在元素时
        int mid = (low + high) / 2; // 求查找区间的中间位置
        compareCount++; // 增加比较次数
        printSubVector(a, low, high); // 打印当前比较的子序列
        
        if (k == a[mid]) { // 找到后返回其物理下标mid
            return mid;
        }
        if (k < a[mid]) { // 当a[mid] > k时，在a[low..mid-1]中递归查找
            return binsearch(a, low, mid - 1, k);
        } else { // 当k > a[mid]时，在a[mid+1..high]中递归查找
            return binsearch(a, mid + 1, high, k);
        }
    }
    else return -1; // 若当前查找区间没有元素时返回-1
}

int binsearch(vector<int>& a, int k) { // 二分查找递归算法
    int n = a.size();
    return binsearch(a, 0, n - 1, k);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int k = 27;
    vector<int> a = {3, 5, 7, 8, 11, 15, 22, 23, 27, 29, 33};
    
    int i = binsearch(a, k);
    
    if (i >= 0)
        printf("a[%d]=%d\n", i, k);
    else
        printf("未找到%d元素\n", k);

    cout << "总共比较了 " << compareCount << " 次" << endl;
    
    return 0;
}

4.假设有14个硬币，编号为0-13，其中编号为12的硬币是假币（假币的重量比真币重），给出采用天平称重方法找出该假币的过程

// By SnowDream
#include<bits/stdc++.h>
using namespace std;

int findFakeCoin(vector<int>& coins, int start, int end) {
    if (start == end) {
        return start; // 如果只剩下一个硬币，则它就是假币
    }

    int mid = (start + end) / 2;
    int leftWeight = 0, rightWeight = 0;

    // 假设所有硬币都是真的，如果发现假币就调整重量
    for (int i = start; i <= end; ++i) {
        if (i <= mid)
            leftWeight+=coins[i];
        else
            rightWeight+=coins[i];

    }

    // 根据哪边更重决定下一步搜索的范围
    if (leftWeight > rightWeight) {
        return findFakeCoin(coins, start, mid);
    } else {
        return findFakeCoin(coins, mid + 1, end);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> coins(14, 0); // 初始化所有硬币为真
    coins[12] = 1; // 设置第12个硬币为假

    int fakeCoinIndex = findFakeCoin(coins, 0, 13);
    cout << "假币的编号是: " << fakeCoinIndex << endl;
    return 0;
}

5.有一个递增有序序列（1,3,5,6,8,10,12），给出查找k=2的插入点的过程

// By SnowDream
#include<bits/stdc++.h>
using namespace std;

// 二分查找找到k的插入点
int findInsertionPoint(const vector<int>& nums, int k) {
    int low = 0, high = nums.size() - 1;
    int mid;

    while (low <= high) {
        mid = low + (high - low) / 2; // 防止溢出
        if (nums[mid] < k) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low; // 返回插入点
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> nums = {1, 3, 5, 6, 8, 10, 12};
    int k = 2;
    int insertionPoint = findInsertionPoint(nums, k);
    cout << "值 " << k << " 的插入点是：" << insertionPoint << endl;
    return 0;
}

P108
例4.3 计算右侧小于当前元素的个数（Leetcode315）
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例

输入：nums = [5,2,6,1]
输出：[2,1,1,0]

// By SnowDream
#include<bits/stdc++.h>
using namespace std;

void mergeSort(vector<int>& nums, vector<int>& indexs, vector<int>& tempindexs,vector<int>& res, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(nums, indexs, tempindexs, res, left, mid);// 递归排序左半部分
    mergeSort(nums, indexs, tempindexs, res, mid + 1, right);// 递归排序右半部分
    int i = left, j = mid + 1, t = 0; // 合并两个已排序的部分
    while (i <= mid && j <= right) {
        if (nums[indexs[i]] > nums[indexs[j]]) {
            for (int k = i; k <= mid; k++) {// 计算右侧元素小于左侧元素的个数
                res[indexs[k]] += (j - mid);
            }
            tempindexs[t++] = indexs[j++];
        } else {
            tempindexs[t++] = indexs[i++];
        }
    }
    while (i <= mid) {   // 将剩余元素复制到临时数组中
        tempindexs[t++] = indexs[i++];
    }
    while (j <= right) {
        tempindexs[t++] = indexs[j++];
    }
    for (int k = left; k <= right; k++) {// 将临时数组中的元素复制回原数组
        indexs[k] = tempindexs[k - left];
    }
}

vector<int> countSmaller(vector<int>& nums) {
    vector<int> res(nums.size(), 0); // 保存结果
    vector<int> indexs(nums.size()); // 索引数组
    for (int i = 0; i < indexs.size(); i++) { // 初始化索引数组
        indexs[i] = i;
    }
    vector<int> tempindexs(indexs.size(), 0); // 临时数组
    mergeSort(nums, indexs, tempindexs, res, 0, nums.size() - 1);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> nums = {5, 2, 6, 1};
    vector<int> ans = countSmaller(nums);
    cout << "每个元素右侧比当前元素小的元素个数：";
    for (int num : ans) {
        cout << num << " ";
    }
    return 0;
}

P111
例4.5 设计一个算法求给定的两个有序序列的中位数
示例

输入：a=(11,13,15,17,19)     b=(2,4,6,8,20)
输出 : 11

// By SnowDream
#include<bits/stdc++.h>
using namespace std;

// 求a[s..t]序列的前半子序列
void prepart(int &s, int &t) {
    int m = (s + t) / 2;
    t = m;
}

// 求a[s..t]序列的后半子序列
void postpart(int &s, int &t) {
    int m = (s + t) / 2;
    if ((t - s + 1) % 2 == 1) // 序列中有奇数个元素
        s = m;
    else                      // 序列中有偶数个元素
        s = m + 1;
}

// 找到两个数组的中位数
int midnum(const int a[], int s1, int t1, const int b[], int s2, int t2) {
    if (s1 == t1 && s2 == t2) // 均只有一个元素时返回较小者
        return min(a[s1], b[s2]);
    else {
        int m1 = (s1 + t1) / 2; // 求a的中位数
        int m2 = (s2 + t2) / 2; // 求b的中位数
        if (a[m1] == b[m2]) // 两中位数相等时返回该中位数
            return a[m1];
        if (a[m1] < b[m2]) { // 当a[m1]<b[m2]时
            postpart(s1, t1); // a取后半部分
            prepart(s2, t2);  // b取前半部分
            return midnum(a, s1, t1, b, s2, t2);
        } else { // 当a[m1]>b[m2]时
            prepart(s1, t1); // a取前半部分
            postpart(s2, t2); // b取后半部分
            return midnum(a, s1, t1, b, s2, t2);
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a[] = {11, 13, 15, 17, 19};
    int b[] = {2, 4, 6, 8, 20};
    int n = sizeof(a) / sizeof(a[0]);
    cout << "中位数: " << midnum(a, 0, n - 1, b, 0, n - 1) << "\n";
    return 0;
}