传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 1643|回复: 2
收起左侧

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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.
. 鍥磋鎴戜滑@1point 3 acres


求问第一周编程题,第一次使用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]复制代码
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
蟹蟹各位啦

. more info on 1point3acres.com
 楼主| yangze0930 发表于 2015-7-8 18:29:47 | 显示全部楼层
重新贴一下代码.鏈枃鍘熷垱鑷1point3acres璁哄潧
vector数据结构写的:
  1. #include<iostream>
  2. #include<vector>
  3. #include<fstream>

  4. using namespace std;

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

  57. . From 1point 3acres bbs
  58. int main(void)
  59. {
  60.         vector<int> a;
  61.         int temp;
  62.         ifstream fin("D:\\IntegerArray.txt");
  63.         if (!fin)
  64.         {
  65.                 cout << "can't open file";
  66.                 return 1;
  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;
  75.         getchar();
  76.         getchar();
  77.         return 0;. 鍥磋鎴戜滑@1point 3 acres
  78. }
复制代码
动态数组写的代码:
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  5. long long inven(int a[],int n)
  6. {. 鍥磋鎴戜滑@1point 3 acres
  7.         if (n != 1). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  8.         {
  9.                 int *b=new int[n/2];
  10.                 int *c=new int[n-n/2];
  11.                 for (int i = 0; i < n / 2; i++). more info on 1point3acres.com
  12.                 {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  13.                         b[i] = a[i];
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  21.                 long long num3 = 0;
  22.                 int i = 0, j = 0;
  23.                 for (int k = 0; k < n; k++)-google 1point3acres
  24.                 {
  25.                         if (i < n / 2 && j<n-n/2)
  26.                         {
  27.                                 if (b[i] <= c[j])
  28.                                 {
  29.                                         a[k] = b[i];
  30.                                         i++;
  31.                                 }. 鍥磋鎴戜滑@1point 3 acres
  32.                                 else if (b[i]>c[j])
  33.                                 {
  34.                                         a[k] = c[j];
  35.                                         num3 = num3 + n / 2 - i;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  36.                                         j++;. visit 1point3acres.com for more.
  37.                                 }
  38.                         }
  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;.1point3acres缃
  54.         }
  55.         else if (n == 1)
  56.                 return 0;
  57. }

  58. int main(void)
  59. {
  60.         ifstream fin("D:\\IntegerArray.txt");
  61.         if (!fin). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  62.         {. more info on 1point3acres.com
  63.                 cout << "can't open file";
  64.                 return 1;
  65.         }
  66.         int a[100000];
  67.         for (int i = 0; i < 100000; i++). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  68.         {. more info on 1point3acres.com
  69.                 fin >> a[i];
  70.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  71.         long long ans = inven(a,100000);
  72.         cout << ans;
  73.         getchar();.1point3acres缃
  74.         getchar();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  75.         return 0;
  76. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| yangze0930 发表于 2015-7-8 18:30:16 | 显示全部楼层
蟹蟹大家啦!!!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-24 17:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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