一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 974|回复: 2
收起左侧

[其他] 求助帖,求问stanford公开课Algorithms: Design and Analysis, Part I (Week 1)的问题

[复制链接] |试试Instant~ |关注本帖
yangze0930 发表于 2015-7-8 18:26:05 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
题目:
Question 1
Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.
.1point3acres缃


求问第一周编程题,第一次使用vector写代码。为什么算出来的结果和用动态数组写的代码算出来的不一样 使用vector写的程序代码,算出来是2584786980.
  • #include<iostream>
  • #include<vector>
  • #include<fstream>
  • using namespace std;
  • long long countInversion(vector<int> & vec)
  • {
  •         int n = vec.size();
  •         if (n != 1)
  •         {
  •                 vector<int> b, c;
  •                 for (int i = 0; i < n / 2; i++)
  •                 {
  •                         b.push_back(vec);
  •                 }
  •                 for (int i = 0; i < n - n / 2; i++)
  •                 {
  •                         c.push_back(vec[n / 2 + i]);
  •                 }
  •                 long long num1 = countInversion(b);
  •                 long long num2 = countInversion(c);
  •                 long long num3 = 0;
  •                 vec.clear();
  •                 int i = 0, j = 0;
  •                 for (int k = 0; k < n; k++)
  •                 {
  •                         if (i < n / 2 && j<n - n / 2)
  •                         {
  •                                 if (b <= c[j])
  •                                 {
  •                                         vec.push_back(b);
  •                                         i++;
  •                                 }
  •                                 else if (b>c[j])
  •                                 {
  •                                         vec.push_back(c);
  •                                         num3 = num3 + n / 2 - i;
  •                                         j++;
  •                                 }
  •                         }
  •                         else if (i >= n / 2)
  •                         {
  •                                 vec.push_back(c[j]);
  •                                 j++;
  •                         }
  •                         else if (j >= n - n / 2)
  •                         {
  •                                 vec.push_back(b);
  •                                 i++;
  •                         }
  •                 }
  •                 long long ans = num1 + num2 + num3;
  •                 return ans;
  •         }
  •         else if (n == 1)
  •                 return 0;
  • }
  • int main(void)
  • {
  •         vector<int> a;
  •         int temp;
  •         ifstream fin("D:\\IntegerArray.txt");
  •         if (!fin)
  •         {
  •                 cout << "can't open file";
  •                 return 1;
  •         }
  •         for (int i = 0; i < 100000; i++)
  •         {
  •                 fin >> temp;
  •                 a.push_back(temp);
  •         }
  •         long long ans = countInversion(a);
  •         cout << a.size()<<'\t'<<ans;
  •         getchar();
  •         getchar();
  •         return 0;
  • }

[color=rgb(73, 123, 137) !important]复制代码

使用动态数组算出来的结果是2407905288
  • #include<iostream>
  • #include<fstream>
  • using namespace std;
  • long long inven(int a[],int n)
  • {
  •         if (n != 1)
  •         {
  •                 int *b=new int[n/2];
  •                 int *c=new int[n-n/2];
  •                 for (int i = 0; i < n / 2; i++)
  •                 {
  •                         b = a;
  •                 }
  •                 for (int i = 0; i < n - n / 2; i++)
  •                 {
  •                         c = a[n / 2 + i];
  •                 }
  •                 long long num1 = inven(b,n/2);
  •                 long long num2 = inven(c,n-n/2);
  •                 long long num3 = 0;
  •                 int i = 0, j = 0;
  •                 for (int k = 0; k < n; k++)
  •                 {
  •                         if (i < n / 2 && j<n-n/2)
  •                         {
  •                                 if (b <= c[j])
  •                                 {
  •                                         a[k] = b;
  •                                         i++;
  •                                 }
  •                                 else if (b>c[j])
  •                                 {
  •                                         a[k] = c[j];
  •                                         num3 = num3 + n / 2 - i;
  •                                         j++;
  •                                 }
  •                         }
  •                         else if (i >= n / 2)
  •                         {
  •                                 a[k] = c[j];
  •                                 j++;
  •                         }
  •                         else if (j >= n - n / 2)
  •                         {
  •                                 a[k] = b;
  •                                 i++;
  •                         }
  •                 }
  •                 delete b;
  •                 delete c;
  •                 long long ans = num1 + num2 + num3;
  •                 return ans;
  •         }
  •         else if (n == 1)
  •                 return 0;
  • }
  • int main(void)
  • {
  •         ifstream fin("D:\\IntegerArray.txt");
  •         if (!fin)
  •         {
  •                 cout << "can't open file";
  •                 return 1;
  •         }
  •         int a[100000];
  •         for (int i = 0; i < 100000; i++)
  •         {
  •                 fin >> a;
  •         }
  •         long long ans = inven(a,100000);
  •         cout << ans;
  •         getchar();
  •         getchar();
  •         return 0;
  • }

[color=rgb(73, 123, 137) !important]复制代码

蟹蟹各位啦. 1point 3acres 璁哄潧


 楼主| yangze0930 发表于 2015-7-8 18:29:47 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
重新贴一下代码
vector数据结构写的:
  1. #include<iostream>
  2. #include<vector>
  3. #include<fstream>

  4. using namespace std;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6. long long countInversion(vector<int> & vec) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  7. {. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.         int n = vec.size();
  9.         if (n != 1)
  10.         {
    . from: 1point3acres.com/bbs
  11.                 vector<int> b, c;
  12.                 for (int i = 0; i < n / 2; i++)
  13.                 {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  14.                         b.push_back(vec[i]);
  15.                 }
  16.                 for (int i = 0; i < n - n / 2; i++). Waral 鍗氬鏈夋洿澶氭枃绔,
  17.                 {
  18.                         c.push_back(vec[n / 2 + i]);
  19.                 }
  20.                 long long num1 = countInversion(b);
  21.                 long long num2 = countInversion(c);
  22.                 long long num3 = 0;
  23.                 vec.clear();
  24.                 int i = 0, j = 0;. 1point 3acres 璁哄潧
  25.                 for (int k = 0; k < n; k++)
  26.                 {
  27.                         if (i < n / 2 && j<n - n / 2)
  28.                         {
  29.                                 if (b[i] <= c[j])
  30.                                 {
  31.                                         vec.push_back(b[i]);
  32.                                         i++;
  33.                                 }
  34.                                 else if (b[i]>c[j]) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  35.                                 {
  36.                                         vec.push_back(c[i]);
  37.                                         num3 = num3 + n / 2 - i;
  38.                                         j++;
  39.                                 }. 鍥磋鎴戜滑@1point 3 acres
  40.                         }. 鍥磋鎴戜滑@1point 3 acres
  41.                         else if (i >= n / 2). From 1point 3acres bbs
  42.                         {
  43.                                 vec.push_back(c[j]);. from: 1point3acres.com/bbs
  44.                                 j++;
  45.                         }
  46.                         else if (j >= n - n / 2). from: 1point3acres.com/bbs
  47.                         {-google 1point3acres
  48.                                 vec.push_back(b[i]);
  49.                                 i++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  50.                         }
  51.                 }
  52.                 long long ans = num1 + num2 + num3;
  53.                 return ans;
  54.         }. From 1point 3acres bbs
  55.         else if (n == 1)
  56.                 return 0;
  57. }


  58. int main(void)
  59. {
  60.         vector<int> a;
  61.         int temp;
  62.         ifstream fin("D:\\IntegerArray.txt");
  63.         if (!fin)
  64.         {.1point3acres缃
  65.                 cout << "can't open file";
  66.                 return 1;. From 1point 3acres bbs
  67.         }
  68.         for (int i = 0; i < 100000; i++)
  69.         {
  70.                 fin >> temp;
  71.                 a.push_back(temp);
  72.         }
  73.         long long ans = countInversion(a);
  74.         cout << a.size()<<'\t'<<ans;. from: 1point3acres.com/bbs
  75.         getchar();
  76.         getchar();
  77.         return 0;
  78. }
复制代码
动态数组写的代码:
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  5. long long inven(int a[],int n)
  6. {
  7.         if (n != 1)
  8.         {
  9.                 int *b=new int[n/2];. 鍥磋鎴戜滑@1point 3 acres
  10.                 int *c=new int[n-n/2];
  11.                 for (int i = 0; i < n / 2; i++). Waral 鍗氬鏈夋洿澶氭枃绔,
  12.                 {-google 1point3acres
  13.                         b[i] = a[i];. From 1point 3acres bbs
  14.                 }
  15.                 for (int i = 0; i < n - n / 2; i++). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.                 {
  17.                         c[i] = a[n / 2 + i];
  18.                 }
  19.                 long long num1 = inven(b,n/2);
  20.                 long long num2 = inven(c,n-n/2);. visit 1point3acres.com for more.
  21.                 long long num3 = 0;
  22.                 int i = 0, j = 0;
  23.                 for (int k = 0; k < n; k++)
  24.                 {
  25.                         if (i < n / 2 && j<n-n/2)
  26.                         {
  27.                                 if (b[i] <= c[j]). Waral 鍗氬鏈夋洿澶氭枃绔,
  28.                                 {
  29.                                         a[k] = b[i];
  30.                                         i++;
  31.                                 }
  32.                                 else if (b[i]>c[j])
  33.                                 {.1point3acres缃
  34.                                         a[k] = c[j];
  35.                                         num3 = num3 + n / 2 - i;
  36.                                         j++;
  37.                                 }
  38.                         }. 鍥磋鎴戜滑@1point 3 acres
  39.                         else if (i >= n / 2)
  40.                         {
  41.                                 a[k] = c[j];
  42.                                 j++;
  43.                         }
  44.                         else if (j >= n - n / 2)
  45.                         {
  46.                                 a[k] = b[i];
  47.                                 i++;
  48.                         }
  49.                 }
  50.                 delete b; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  51.                 delete c;
  52.                 long long ans = num1 + num2 + num3;
  53.                 return ans;
  54.         }. from: 1point3acres.com/bbs
  55.         else if (n == 1)
  56.                 return 0;
  57. }
  58. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  59. int main(void)
  60. {
  61.         ifstream fin("D:\\IntegerArray.txt");
  62.         if (!fin)
  63.         {
  64.                 cout << "can't open file";
  65.                 return 1;
  66.         }. visit 1point3acres.com for more.
  67.         int a[100000];. from: 1point3acres.com/bbs
  68.         for (int i = 0; i < 100000; i++)
  69.         {. more info on 1point3acres.com
  70.                 fin >> a[i];
  71.         }
  72.         long long ans = inven(a,100000);
  73.         cout << ans;
  74.         getchar();
  75.         getchar();
  76.         return 0;
  77. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| yangze0930 发表于 2015-7-8 18:30:16 | 显示全部楼层
关注一亩三分地微博:
Warald
蟹蟹大家啦!!!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-3-25 08:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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