算法设计与分析课程设计

算法设计与分析课程设计

/ 0评 / 3037次 / 2赞

基于分治法的大整数乘法

  1. /*
  2. * @Author : Gehrychiang
  3. * @LastEditTime : 2021-06-15 14:31:31
  4. * @Website : www.yilantingfeng.site
  5. * @E-mail : gehrychiang@aliyun.com
  6. * @ProbTitle : 大整数乘法
  7. */
  8. //#pragma GCC optimize(2)
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  12. const int dMax = 1000;
  13. struct calNode
  14. {
  15. char s[dMax + 5];
  16. int length = 0; //s的有效数位长度
  17. int powNum = 0; //10^powNum
  18. calNode()
  19. {
  20. memset(s, 0, sizeof(s));
  21. length = 0;
  22. powNum = 0;
  23. }
  24. calNode(string in)
  25. {
  26. calNode();
  27. for (int i = 0; i < in.length(); i++)
  28. {
  29. s[length++] = in[i];
  30. }
  31. standardize();
  32. }
  33. calNode(ll in)
  34. {
  35. calNode();
  36. while (in)
  37. {
  38. s[length++] = char((in % 10) + '0');
  39. in /= 10;
  40. }
  41. for (int i = 0; i < length / 2; i++)
  42. {
  43. swap(s[i], s[length - i - 1]);
  44. }
  45. standardize();
  46. }
  47. calNode operator+(const calNode &b) const
  48. {
  49. calNode ret = calNode();
  50. ret.powNum = min(powNum, b.powNum);
  51. int flag = 0;
  52. for (int i = min(powNum, b.powNum); i < max(powNum + length, b.powNum + b.length) + 1; i++)
  53. {
  54. int left = ((i - powNum) >= 0 && i < length + powNum) ? s[length - 1 - i + powNum] - '0' : 0;
  55. int right = ((i - b.powNum) >= 0 && i < b.length + b.powNum) ? b.s[b.length - 1 - i + b.powNum] - '0' : 0;
  56. if (i == max(powNum + length, b.powNum + b.length) && flag == 0)
  57. {
  58. break;
  59. }
  60. ret.s[ret.length++] = char((left + right + flag) % 10 + '0');
  61. flag = (left + right + flag) / 10;
  62. }
  63. for (int i = 0; i < ret.length / 2; i++)
  64. {
  65. swap(ret.s[i], ret.s[ret.length - i - 1]);
  66. }
  67. ret.standardize();
  68. return ret;
  69. }
  70. void standardize()
  71. {
  72. while (length > 1 && s[length - 1] == '0')
  73. {
  74. length--;
  75. powNum++;
  76. }
  77. }
  78. bool read()
  79. {
  80. scanf("%s", s);
  81. length = strlen(s);
  82. bool preZero = false;
  83. for (int i = 0; i < length; i++)
  84. {
  85. if (s[i] == '0' && !preZero) //前导0
  86. {
  87. return false;
  88. }
  89. if (s[i] < '0' || s[i] > '9') //不合法数字
  90. {
  91. return false;
  92. }
  93. if (s[i] != '0' && !preZero) //允许前导0
  94. {
  95. preZero = true;
  96. }
  97. }
  98. standardize();
  99. return true;
  100. }
  101. void write()
  102. {
  103. printf("%s", s);
  104. if (powNum != 0)
  105. {
  106. for (int i = 0; i < powNum; i++)
  107. {
  108. printf("0");
  109. }
  110. }
  111. printf("\n");
  112. }
  113. bool smallerThanInt()
  114. {
  115. if (length <= 9)
  116. {
  117. return true;
  118. }
  119. else
  120. {
  121. return false;
  122. }
  123. }
  124. int toInt()
  125. {
  126. int ret = 0;
  127. int tmp = 1;
  128. for (int i = length - 1; i >= 0; i--)
  129. {
  130. ret += (s[i] - '0') * tmp;
  131. tmp *= 10;
  132. }
  133. return ret;
  134. }
  135. pair<calNode, calNode> divide()
  136. {
  137. calNode highNum = calNode();
  138. calNode lowNum = calNode();
  139. for (int i = 0; i < length; i++)
  140. {
  141. if (i < length / 2)
  142. {
  143. highNum.s[highNum.length++] = s[i];
  144. }
  145. else
  146. {
  147. lowNum.s[lowNum.length++] = s[i];
  148. }
  149. highNum.powNum = powNum + ((length + 1) / 2);
  150. lowNum.powNum = powNum;
  151. }
  152. return make_pair(highNum, lowNum);
  153. }
  154. };
  156. calNode multiply(calNode calA, calNode calB)
  157. {
  158. if (calA.smallerThanInt() && calB.smallerThanInt())
  159. {
  160. calNode ret = calNode((ll)calA.toInt() * calB.toInt());
  161. ret.powNum = calA.powNum + calB.powNum;
  162. return ret;
  163. }
  164. else if (calB.smallerThanInt())
  165. {
  166. calNode calAHigh = calNode();
  167. calNode calALow = calNode();
  168. pair<calNode, calNode> res = calA.divide();
  169. calAHigh = res.first;
  170. calALow = res.second;
  171. return multiply(calAHigh, calB) + multiply(calALow, calB);
  172. }
  173. else
  174. {
  175. calNode calBHigh = calNode();
  176. calNode calBLow = calNode();
  177. pair<calNode, calNode> res = calB.divide();
  178. calBHigh = res.first;
  179. calBLow = res.second;
  180. return multiply(calA, calBHigh) + multiply(calA, calBLow);
  181. }
  182. }
  183. int main()
  184. {
  185. //freopen("","r",stdin);
  186. //freopen("","w",stdout);
  187. calNode a = calNode();
  188. a.read();
  189. calNode b = calNode();
  190. b.read();
  191. multiply(a, b).write();
  192. return 0;
  193. }
/*
 * @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;
}

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

  1. /*
  2. * @Author : Gehrychiang
  3. * @LastEditTime : 2021-06-15 14:04:35
  4. * @Website : www.yilantingfeng.site
  5. * @E-mail : gehrychiang@aliyun.com
  6. * @ProbTitle : 导弹拦截
  7. */
  8. //#pragma GCC optimize(2)
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. int a[100005];
  12. int ss[100005];
  13. int main()
  14. {
  15. //freopen("","r",stdin);
  16. //freopen("","w",stdout);
  17. ios_base::sync_with_stdio(false);
  18. cin.tie(NULL);
  19. int n = 0;
  20. while (cin >> a[n])
  21. {
  22. n++;
  23. }
  24. //打一个lis
  25. ss[0] = a[n - 1];
  26. int len = 1;
  27. for (int i = n - 2; i >= 0; i--)
  28. {
  29. if (a[i] >= ss[len - 1])
  30. {
  31. ss[len++] = a[i];
  32. }
  33. else
  34. {
  35. ss[upper_bound(ss, ss + len, a[i]) - ss] = a[i];
  36. }
  37. }
  38. cout << len << endl;
  39. memset(ss, 0, sizeof(ss));
  40. ss[0] = a[0];
  41. len = 1;
  42. for (int i = 1; i < n; i++)
  43. {
  44. if (a[i] > ss[len - 1])
  45. {
  46. ss[len++] = a[i];
  47. }
  48. else
  49. {
  50. ss[lower_bound(ss, ss + len, a[i]) - ss] = a[i];
  51. }
  52. }
  53. cout << len << endl;
  54. return 0;
  55. }
/*
 * @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;
}

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

  1. /*
  2. * @Author : Gehrychiang
  3. * @LastEditTime : 2021-06-15 14:14:36
  4. * @Website : www.yilantingfeng.site
  5. * @E-mail : gehrychiang@aliyun.com
  6. * @ProbTitle : 歌曲磁带问题
  7. */
  8. //#pragma GCC optimize(2)
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  12. const int N = 10000;
  13. int a[N + 5];
  14. int main()
  15. {
  16. //freopen("","r",stdin);
  17. //freopen("","w",stdout);
  18. int n;
  19. scanf("%d", &n);
  20. for (int i = 0; i < n; i++)
  21. {
  22. scanf("%d", &a[i]);
  23. }
  24. //考虑a[i]与a[i+1]的顺序关系
  25. //之前与之后的所有曲子的加载时间不会因为a[i]与a[i+1]的顺序关系产生改变，故只需考察a[i]与a[i+1]的顺序何者更优
  26. //如a[i]在前a[i+1]在后 则a[i]的加载时间为T,a[i+1]的加载时间为T+a[i]
  27. //如a[i+1]在前a[i]在后 则a[i]的加载时间为T+a[i+1],a[i+1]的加载时间为T
  28. //显然要是总和最小，即使歌曲按时长从小大到大排序即可
  29. sort(a, a + n);
  30. for (int i = 0; i < n; i++)
  31. {
  32. printf("%d", a[i]);
  33. }
  34. return 0;
  35. }
/*
 * @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;
}

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

  1. /*
  2. * @Author : Gehrychiang
  3. * @LastEditTime : 2021-06-15 14:27:15
  4. * @Website : www.yilantingfeng.site
  5. * @E-mail : gehrychiang@aliyun.com
  6. * @ProbTitle : 图的m着色问题
  7. */
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. const int N = 4;
  11. int gra[N + 5][N + 5];
  12. int ans[N + 5];
  13. int n, m, flag;
  14. bool chk(int curLevel, int curColor)
  15. {
  16. for (int i = 1; i < curLevel; i++)
  17. {
  18. //check i and curLev conflict
  19. if (gra[curLevel][i] == 1 && ans[i] == curColor)
  20. {
  21. return false;
  22. }
  23. }
  24. return true;
  25. }
  26. void dfs(int curLevel)
  27. {
  28. if (curLevel == n + 1)
  29. {
  30. if (flag == 0)
  31. {
  32. cout << "Vertices: ";
  33. for (int i = 1; i <= n; i++)
  34. {
  35. cout << i << " ";
  36. }
  37. flag++;
  38. }
  39. cout << "Color: ";
  40. for (int i = 1; i <= n; i++)
  41. {
  42. cout << ans[i] << " ";
  43. }
  44. cout << endl;
  45. return;
  46. }
  47. for (int i = 1; i <= m; i++)
  48. {
  49. if (chk(curLevel, i))
  50. {
  51. ans[curLevel] = i;
  52. dfs(curLevel + 1);
  53. ans[curLevel] = 0;
  54. }
  55. }
  56. }
  57. int main()
  58. {
  59. cin >> n;
  60. int k;
  61. cin >> k;
  62. for (int i = 0; i < k; i++)
  63. {
  64. int a, b;
  65. cin >> a >> b;
  66. gra[a][b] = 1;
  67. gra[b][a] = 1;
  68. }
  69. cin >> m;
  70. dfs(1);
  71. if (flag == 0)
  72. {
  73. cout << "No solution";
  74. }
  75. else
  76. {
  77. cout << "Total count is " + flag;
  78. }
  79. return 0;
  80. }
  82. /*
  83. 5
  84. 9
  85. 1 2
  86. 1 3
  87. 1 4
  88. 2 3
  89. 2 4
  90. 2 5
  91. 3 4
  92. 3 5
  93. 4 5
  94. 4
  95. */
/*
 * @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.98436