算法设计练习

admin2024-04-03  0

回文判断问题:

回文是指特殊的字符串,它从头到尾读与从尾到头读的内容是一致的,比如说“doggod”,无论从左到右耗时从右到左都是一样的。使用递归算法判断一个字符串是否为回文,如果是返回1,不是返回0。在主函数中输入一个字符串,并通过该递归函数进行判断,并输出结果。

#include <iostream>

#include <string>



using namespace std;



bool is_palindrome(string s, int start, int end) {

    if (start >= end)

        return true;

    if (s[start] != s[end])

        return false;

    return is_palindrome(s, start + 1, end - 1);

}



int main() {

    string input;

    cout << "请输入一个字符串:";

    cin >> input;

    if (is_palindrome(input, 0, input.length() - 1))

        cout << "是回文" << endl;

    else

        cout << "不是回文" << endl;

    return 0;

}

二分查找问题:

对从大到小顺序的数据进行二分查找,并要求使用递归函数实现该二分查找,如果找到则返回该数据的所在的位置,如果找不到则返回-1。在主函数中输入从大到小顺序的数据进和要查找的数据,并通过该递归函数进行查找,并输出结果

#include <iostream>

#include <vector>



using namespace std;



int binary_search_recursive(vector<int>& arr, int target, int left, int right) {

    if (left <= right) {

        int mid = left + (right - left) / 2;

        if (arr[mid] == target)

            return mid;

        else if (arr[mid] > target)

            return binary_search_recursive(arr, target, mid + 1, right);

        else

            return binary_search_recursive(arr, target, left, mid - 1);

    }

    return -1;

}



int main() {

    vector<int> data;

    int n, target;



    cout << "请输入数据个数:";

    cin >> n;

    cout << "请输入从大到小顺序的数据:" << endl;

    for (int i = 0; i < n; ++i) {

        int value;

        cin >> value;

        data.push_back(value);

    }



    cout << "请输入要查找的数据:";

    cin >> target;



    int result = binary_search_recursive(data, target, 0, n - 1);

    if (result != -1)

        cout << "数据 " << target << " 所在位置为:" << result << endl;

    else

        cout << "数据 " << target << " 未找到" << endl;



    return 0;

}

归并排序:

用递归算法实现归并排序,在主函数中输入一些数据,并通过该递归函数进行排序,并将排序结果输出。

#include <iostream>

#include <vector>



using namespace std;



void merge(vector<int>& arr, int left, int mid, int right) {

    int n1 = mid - left + 1;

    int n2 = right - mid;



    vector<int> L(n1);

    vector<int> R(n2);



    for (int i = 0; i < n1; ++i)

        L[i] = arr[left + i];

    for (int j = 0; j < n2; ++j)

        R[j] = arr[mid + 1 + j];



    int i = 0;

    int j = 0;

    int k = left;



    while (i < n1 && j < n2) {

        if (L[i] >= R[j]) {

            arr[k] = L[i];

            i++;

        }

        else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }



    while (i < n1) {

        arr[k] = L[i];

        i++;

        k++;

    }



    while (j < n2) {

        arr[k] = R[j];

        j++;

        k++;

    }

}



void merge_sort(vector<int>& arr, int left, int right) {

    if (left < right) {

        int mid = left + (right - left) / 2;



        merge_sort(arr, left, mid);

        merge_sort(arr, mid + 1, right);



        merge(arr, left, mid, right);

    }

}



int main() {

    vector<int> data;

    int n;



    cout << "请输入数据个数:";

    cin >> n;

    cout << "请输入数据:" << endl;

    for (int i = 0; i < n; ++i) {

        int value;

        cin >> value;

        data.push_back(value);

    }



    merge_sort(data, 0, n - 1);



    cout << "排序结果:" << endl;

    for (int i = 0; i < n; ++i) {

        cout << data[i] << " ";

    }

    cout << endl;



    return 0;

}

求一组数中的第二大数问题:

用递归算法实现从一组数据中找出第二大的数,并将该数进行返回,在主函数中输入一些数据,并通过调用该递归函数求出第二大的数,并将结果输出。

#include <iostream>

#include <vector>



using namespace std;



pair<int, int> find_second_largest_helper(vector<int>& arr, int start, int end) {

    if (start == end) {

        return { arr[start], INT_MIN };

    }

    else {

        int mid = start + (end - start) / 2;

        auto left = find_second_largest_helper(arr, start, mid);

        auto right = find_second_largest_helper(arr, mid + 1, end);



        int largest = max(left.first, right.first);

        int second_largest = max(min(left.first, right.first), max(left.second, right.second));



        return { largest, second_largest };

    }

}



int find_second_largest(vector<int>& arr) {

    auto result = find_second_largest_helper(arr, 0, arr.size() - 1);

    return result.second;

}



int main() {

    vector<int> data;

    int n;



    cout << "请输入数据个数:";

    cin >> n;

    cout << "请输入数据:" << endl;

    for (int i = 0; i < n; ++i) {

        int value;

        cin >> value;

        data.push_back(value);

    }



    int second_largest = find_second_largest(data);

    cout << "第二大的数是:" << second_largest << endl;



    return 0;

}

最大子段和问题:

给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0,依此定义,所求的最优值为: Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如,当(a[1],a[2],a[3],a[4],a[5],a[6])=(-20,11,-4,13,-5,-2)时,最大子段和为20(11,-4,13)。(使用蛮力算法和分治算法分别实现)

源程序及运行结果:

蛮力算法:

#include <iostream>

#include <vector>



using namespace std;



int max_subarray_brute_force(vector<int>& nums) {

    int n = nums.size();

    int max_sum = 0;



    for (int i = 0; i < n; ++i) {

        for (int j = i; j < n; ++j) {

            int sum = 0;

            for (int k = i; k <= j; ++k) {

                sum += nums[k];

            }

            max_sum = max(max_sum, sum);

        }

    }



    return max_sum;

}



int main() {

    vector<int> nums = { -20, 11, -4, 13, -5, -2 };

    int max_sum = max_subarray_brute_force(nums);

    cout << "最大子段和为: " << max_sum << endl;



    return 0;

}

分治算法:

#include <iostream>

#include <vector>



using namespace std;



int max_crossing_subarray(vector<int>& nums, int low, int mid, int high) {

    int left_sum = INT_MIN;

    int sum = 0;

    for (int i = mid; i >= low; --i) {

        sum += nums[i];

        if (sum > left_sum)

            left_sum = sum;

    }



    int right_sum = INT_MIN;

    sum = 0;

    for (int j = mid + 1; j <= high; ++j) {

        sum += nums[j];

        if (sum > right_sum)

            right_sum = sum;

    }



    return left_sum + right_sum;

}



int max_subarray_divide_and_conquer(vector<int>& nums, int low, int high) {

    if (low == high)

        return nums[low];



    int mid = (low + high) / 2;



    int left_max = max_subarray_divide_and_conquer(nums, low, mid);

    int right_max = max_subarray_divide_and_conquer(nums, mid + 1, high);

    int cross_max = max_crossing_subarray(nums, low, mid, high);



    return max({ left_max, right_max, cross_max });

}



int main() {

    vector<int> nums = { -20, 11, -4, 13, -5, -2 };

    int max_sum = max_subarray_divide_and_conquer(nums, 0, nums.size() - 1);

    cout << "最大子段和为: " << max_sum << endl;



    return 0;

}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!