算法设计与分析课程设计

算法设计与分析课程设计

/ 0评 / 1994次 / 2

基于分治法的大整数乘法

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2021-06-15 14:31:31
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : 大整数乘法
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int dMax = 1000;
struct calNode
{
    char s[dMax + 5];
    int length = 0; //s的有效数位长度
    int powNum = 0; //10^powNum
    calNode()
    {
        memset(s, 0, sizeof(s));
        length = 0;
        powNum = 0;
    }
    calNode(string in)
    {
        calNode();
        for (int i = 0; i < in.length(); i++)
        {
            s[length++] = in[i];
        }
        standardize();
    }
    calNode(ll in)
    {
        calNode();
        while (in)
        {
            s[length++] = char((in % 10) + '0');
            in /= 10;
        }
        for (int i = 0; i < length / 2; i++)
        {
            swap(s[i], s[length - i - 1]);
        }
        standardize();
    }
    calNode operator+(const calNode &b) const
    {
        calNode ret = calNode();
        ret.powNum = min(powNum, b.powNum);
        int flag = 0;
        for (int i = min(powNum, b.powNum); i < max(powNum + length, b.powNum + b.length) + 1; i++)
        {
            int left = ((i - powNum) >= 0 && i < length + powNum) ? s[length - 1 - i + powNum] - '0' : 0;
            int right = ((i - b.powNum) >= 0 && i < b.length + b.powNum) ? b.s[b.length - 1 - i + b.powNum] - '0' : 0;
            if (i == max(powNum + length, b.powNum + b.length) && flag == 0)
            {
                break;
            }
            ret.s[ret.length++] = char((left + right + flag) % 10 + '0');
            flag = (left + right + flag) / 10;
        }
        for (int i = 0; i < ret.length / 2; i++)
        {
            swap(ret.s[i], ret.s[ret.length - i - 1]);
        }
        ret.standardize();
        return ret;
    }
    void standardize()
    {
        while (length > 1 && s[length - 1] == '0')
        {
            length--;
            powNum++;
        }
    }
    bool read()
    {
        scanf("%s", s);
        length = strlen(s);
        bool preZero = false;
        for (int i = 0; i < length; i++)
        {
            if (s[i] == '0' && !preZero) //前导0
            {
                return false;
            }
            if (s[i] < '0' || s[i] > '9') //不合法数字
            {
                return false;
            }
            if (s[i] != '0' && !preZero) //允许前导0
            {
                preZero = true;
            }
        }
        standardize();
        return true;
    }
    void write()
    {
        printf("%s", s);
        if (powNum != 0)
        {
            for (int i = 0; i < powNum; i++)
            {
                printf("0");
            }
        }
        printf("\n");
    }
    bool smallerThanInt()
    {
        if (length <= 9)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    int toInt()
    {
        int ret = 0;
        int tmp = 1;
        for (int i = length - 1; i >= 0; i--)
        {
            ret += (s[i] - '0') * tmp;
            tmp *= 10;
        }
        return ret;
    }
    pair<calNode, calNode> divide()
    {
        calNode highNum = calNode();
        calNode lowNum = calNode();
        for (int i = 0; i < length; i++)
        {
            if (i < length / 2)
            {
                highNum.s[highNum.length++] = s[i];
            }
            else
            {
                lowNum.s[lowNum.length++] = s[i];
            }
            highNum.powNum = powNum + ((length + 1) / 2);
            lowNum.powNum = powNum;
        }
        return make_pair(highNum, lowNum);
    }
};

calNode multiply(calNode calA, calNode calB)
{
    if (calA.smallerThanInt() && calB.smallerThanInt())
    {
        calNode ret = calNode((ll)calA.toInt() * calB.toInt());
        ret.powNum = calA.powNum + calB.powNum;
        return ret;
    }
    else if (calB.smallerThanInt())
    {
        calNode calAHigh = calNode();
        calNode calALow = calNode();
        pair<calNode, calNode> res = calA.divide();
        calAHigh = res.first;
        calALow = res.second;
        return multiply(calAHigh, calB) + multiply(calALow, calB);
    }
    else
    {
        calNode calBHigh = calNode();
        calNode calBLow = calNode();
        pair<calNode, calNode> res = calB.divide();
        calBHigh = res.first;
        calBLow = res.second;
        return multiply(calA, calBHigh) + multiply(calA, calBLow);
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    calNode a = calNode();
    a.read();
    calNode b = calNode();
    b.read();
    multiply(a, b).write();
    return 0;
}

基于动态规划的导弹拦截问题

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2021-06-15 14:04:35
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : 导弹拦截
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int ss[100005];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n = 0;
    while (cin >> a[n])
    {
        n++;
    }
    //打一个lis
    ss[0] = a[n - 1];
    int len = 1;
    for (int i = n - 2; i >= 0; i--)
    {
        if (a[i] >= ss[len - 1])
        {
            ss[len++] = a[i];
        }
        else
        {
            ss[upper_bound(ss, ss + len, a[i]) - ss] = a[i];
        }
    }
    cout << len << endl;
    memset(ss, 0, sizeof(ss));
    ss[0] = a[0];
    len = 1;
    for (int i = 1; i < n; i++)
    {
        if (a[i] > ss[len - 1])
        {
            ss[len++] = a[i];
        }
        else
        {
            ss[lower_bound(ss, ss + len, a[i]) - ss] = a[i];
        }
    }
    cout << len << endl;
    return 0;
}

利用贪心算法的唱片规划问题

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2021-06-15 14:14:36
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : 歌曲磁带问题
 */
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000;
int a[N + 5];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    //考虑a[i]与a[i+1]的顺序关系
    //之前与之后的所有曲子的加载时间不会因为a[i]与a[i+1]的顺序关系产生改变,故只需考察a[i]与a[i+1]的顺序何者更优
    //如a[i]在前a[i+1]在后 则a[i]的加载时间为T,a[i+1]的加载时间为T+a[i]
    //如a[i+1]在前a[i]在后 则a[i]的加载时间为T+a[i+1],a[i+1]的加载时间为T
    //显然要是总和最小,即使歌曲按时长从小大到大排序即可
    sort(a, a + n);
    for (int i = 0; i < n; i++)
    {
        printf("%d", a[i]);
    }
    return 0;
}

基于回溯剪枝策略的图着色问题

/*
 * @Author       : Gehrychiang
 * @LastEditTime : 2021-06-15 14:27:15
 * @Website      : www.yilantingfeng.site
 * @E-mail       : gehrychiang@aliyun.com
 * @ProbTitle    : 图的m着色问题
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 4;
int gra[N + 5][N + 5];
int ans[N + 5];
int n, m, flag;
bool chk(int curLevel, int curColor)
{
    for (int i = 1; i < curLevel; i++)
    {
        //check i and curLev conflict
        if (gra[curLevel][i] == 1 && ans[i] == curColor)
        {
            return false;
        }
    }
    return true;
}
void dfs(int curLevel)
{
    if (curLevel == n + 1)
    {
        if (flag == 0)
        {
            cout << "Vertices: ";
            for (int i = 1; i <= n; i++)
            {
                cout << i << " ";
            }
            flag++;
        }
        cout << "Color: ";
        for (int i = 1; i <= n; i++)
        {
            cout << ans[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= m; i++)
    {
        if (chk(curLevel, i))
        {
            ans[curLevel] = i;
            dfs(curLevel + 1);
            ans[curLevel] = 0;
        }
    }
}
int main()
{
    cin >> n;
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        int a, b;
        cin >> a >> b;
        gra[a][b] = 1;
        gra[b][a] = 1;
    }
    cin >> m;
    dfs(1);
    if (flag == 0)
    {
        cout << "No solution";
    }
    else
    {
        cout << "Total count is " + flag;
    }
    return 0;
}

/*
5
9
1 2
1 3
1 4
2 3
2 4
2 5
3 4
3 5
4 5
4
*/

发表回复

您的电子邮箱地址不会被公开。

你好 No.65347