📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1720| 回复: 7
跳转到指定楼层
上一主题 下一主题
收起左侧

[Stanford Algorithm] Divide and Conquer, Sorting and Searching, and Randomize

全局:
公开课
学校名称: 哈尔滨工业大学
Unit号: 9
开课时间: 2019-09-23
课程全名: algorithms-divide-conquer
平台: Coursera
URL: https://www.coursera.org/learn/algorithms-divide-conquer

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
之前高中搞过信息学竞赛,拿了个省一就不玩了..大学读的偏偏又是EE,现在申请需要一些证明CS背景的东西,很头疼。
看了下地里推荐的课程内容,感觉实际上内容之前都已经学过了,完全就是为了证明背景上的课..虽然也不知道有没有什么用
在这里发帖来监督自己打个卡..

上一篇:CS224n: Natural Language Processing with Deep Learning
下一篇:求组队上music theory公开课
🔗
 楼主| kningtg 2019-9-25 20:43:44 | 只看该作者
全局:
尴尬了,才发现自己没有注册课程!压根提交不了代码!

完成了WEEK 1的Karatsuba Multiplication
实现的大概思路无非就是用string去存储大数,然后按部就班就好
但是这里有个实现的细节值得注意,由于我们这里mult的实现是对数字进行不断二分,所以我们需要把长度补齐为n的二次幂,这个并不会影响算法的复杂度(顶多常数变大而已)

  1. #include<cstdio>
  2. #include<iostream>
  3. #include<string>
  4. #include<cstring>
  5. using namespace std;

  6. string add(string a, string b)
  7. {
  8.     int n = max(a.length(), b.length());
  9.     while (n > a.length())
  10.     {
  11.         a = "0" + a;
  12.     }
  13.     while (n > b.length())
  14.     {
  15.         b = "0" + b;
  16.     }
  17.     int tmp[100];
  18.     string ret;
  19.     memset(tmp, 0, sizeof(tmp));
  20.     int next = 0;
  21.     for (int i=0; i<n; i++)
  22.     {
  23.         int cur = a[n-i-1] + b[n-i-1] - '0' - '0' + next;
  24.         next = 0;
  25.         if (cur >= 10)
  26.         {
  27.             cur -= 10;
  28.             next = 1;
  29.         }
  30.         ret = char(cur + '0') + ret;
  31.     }
  32.     if (next != 0)
  33.     {
  34.         ret = "1" + ret;
  35.     }
  36.     while (ret[0] == '0') ret = ret.substr(1, ret.length()-1);
  37.     return ret;
  38. }

  39. string subt(string a, string b)
  40. {
  41.     int n = max(a.length(), b.length());
  42.     while (n > a.length())
  43.     {
  44.         a = "0" + a;
  45.     }
  46.     while (n > b.length())
  47.     {
  48.         b = "0" + b;
  49.     }
  50.     int tmp[100];
  51.     string ret;
  52.     memset(tmp, 0, sizeof(tmp));
  53.     int next = 0;
  54.     for (int i=0; i<n; i++)
  55.     {
  56.         int cur = a[n-i-1] - b[n-i-1] + next;
  57.         next = 0;
  58.         if (cur < 0)
  59.         {
  60.             cur += 10;
  61.             next = -1;
  62.         }
  63.         ret = char(cur + '0') + ret;
  64.     }
  65.     while (ret[0] == '0') ret = ret.substr(1, ret.length()-1);
  66.     return ret;
  67. }

  68. string add_zero(string arr, int n)
  69. {
  70.     for (int i=0; i<n; i++)
  71.     {
  72.         arr = arr + "0";
  73.     }
  74.     return arr;
  75. }

  76. string calc(string x, string y)
  77. {
  78.     // cout << "-----------------------------------\n";
  79.     int n = max(x.length(), y.length());
  80.     int cnt = 1;
  81.     while (cnt < n)
  82.     {
  83.         cnt <<= 1;
  84.     }
  85.     n = cnt;
  86.     while (n > x.length())
  87.     {
  88.         x = "0" + x;
  89.     }
  90.     while (n > y.length())
  91.     {
  92.         y = "0" + y;
  93.     }
  94.     if (x.length() == 1 and y.length() == 1)
  95.     {
  96.         string ret = "";
  97.         int num = (x[0] - '0') * (y[0] - '0');
  98.         if (num/10 != 0)
  99.         {
  100.             ret += char(num / 10 + '0');
  101.         }
  102.         num %= 10;
  103.         ret += char(num + '0');
  104.         return ret;
  105.     }
  106.     if (n == 0)
  107.     {
  108.         return "0";
  109.     }
  110.     // cout << "n:" << n << "\n";
  111.     string a = x.substr(0, n / 2);
  112.     string b = x.substr(n / 2, n / 2);
  113.     string c = y.substr(0, n / 2);
  114.     string d = y.substr(n / 2, n / 2);
  115.     // cout << "x:" << x << "\ty:" << y << "\n";
  116.     // cout << "a:" << a << "\tb:" << b << "\tc:" << c << "\td:" <<d << "\n";

  117.     string ac = calc(a, c);
  118.     string bd = calc(b, d);
  119.     string sum = calc(add(a, b), add(c, d));
  120.     string mid_term = subt(subt(sum, ac), bd);
  121.     ac = add_zero(ac, n);
  122.     mid_term = add_zero(mid_term, n/2);
  123.     // cout << "ac:" << ac << "\tbd:" << bd << "\tmid_term:" << mid_term << "\tsum:" << sum << "\n";
  124.     return add(add(ac, mid_term), bd);
  125. }

  126. int main()
  127. {
  128.     freopen("in.txt", "r", stdin);
  129.     ios::sync_with_stdio(false);
  130.     string a, b;
  131.     cin >> a >> b;
  132.     cout << calc(a, b) << "\n";
  133.     return 0;
  134. }
复制代码
回复

使用道具 举报

🔗
TimothyRayZ 2019-11-28 09:54:10 | 只看该作者
全局:
我也在看Stanford的Algorithm,借你的帖一起学习!
回复

使用道具 举报

🔗
 楼主| kningtg 2019-11-28 17:07:25 | 只看该作者
全局:
TimothyRayZ 发表于 2019-11-28 09:54
我也在看Stanford的Algorithm,借你的帖一起学习!

惊了我还以为这个帖子早就沉了,hhhh
回复

使用道具 举报

🔗
TimothyRayZ 2019-11-28 17:12:59 | 只看该作者
全局:
kningtg 发表于 2019-11-28 17:07
惊了我还以为这个帖子早就沉了,hhhh

才看到这帖子时间好早...所以bro你已经上完了吧?
回复

使用道具 举报

🔗
 楼主| kningtg 2019-11-28 17:16:49 | 只看该作者
全局:
TimothyRayZ 发表于 2019-11-28 17:12
才看到这帖子时间好早...所以bro你已经上完了吧?

当时还没正式注册..就没有提交代码,最近才刚过的financial aid,还是可以一起上的hh
虽说最近在看高等代数之类数学系的东西...Sigh..要学的实在太多了
回复

使用道具 举报

全局:
kningtg 发表于 2019/11/28 17:16:49
当时还没正式注册..就没有提交代码,最近才刚过的financial aid,还是可以一起上的hh
虽说最近在看高等代数...
一起加油8,我也是EE的,北理16级,准备往CS方向靠一靠,最近也在补离散数学之类的cs课...
回复

使用道具 举报

🔗
 楼主| kningtg 2019-11-28 17:49:51 | 只看该作者
全局:
TimothyRayZ 发表于 2019-11-28 17:31
一起加油8,我也是EE的,北理16级,准备往CS方向靠一靠,最近也在补离散数学之类的cs课...

好哈哈哈~一起加油!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表