c*****e
发帖数: 74 | 1 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
次都只做了一道题，太慢了，看看别人都是好几道题。 |
c*******t
发帖数: 12 | |
l*********r
发帖数: 674 | 3 同问，分享一下方程的形式把。还从来没见过这种类型的面试题呢，应改不是单纯的做
数学题把，是不是有什么trick在里面。
【在 c*******t 的大作中提到】
: 是二次方程还是高次的？
|
c*****e
发帖数: 74 | 4 没有什么trick，就是解一个正正数系数方程，多元一次。不是数学题，是编程题。
【在 l*********r 的大作中提到】
: 同问，分享一下方程的形式把。还从来没见过这种类型的面试题呢，应改不是单纯的做
: 数学题把，是不是有什么trick在里面。
|
c*****e
发帖数: 74 | 5 多元一次。
【在 c*******t 的大作中提到】
: 是二次方程还是高次的？
|
L*******r
发帖数: 5448 | 6 多元一次不就是线性方程组吗
【在 c*****e 的大作中提到】
: 多元一次。
|
v***n
发帖数: 5085 | 7 LU decomposition? G-S? SD? |
g*********s
发帖数: 1782 | 8 正整数系数多元一次方程，求所有非负整数解？
这不就是print_all_coin_combination()吗？
【在 c*****e 的大作中提到】
: 没有什么trick，就是解一个正正数系数方程，多元一次。不是数学题，是编程题。
|
y****r
发帖数: 39 | |
x**y
发帖数: 70 | 10 数学题当场编程?
【在 c*****e 的大作中提到】
: 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
: 次都只做了一道题，太慢了，看看别人都是好几道题。
|
|
|
g*********s
发帖数: 1782 | 11 楼主没说清楚。方程系数就是硬币面值，解就是硬币个数。等价于给一组硬币和总钱数
，求硬币组合。
【在 y****r 的大作中提到】
: 飞思不可 转行做MATLAB了？
|
c*****e
发帖数: 74 | 12 是的是的，不好意思没说清楚。
【在 g*********s 的大作中提到】
: 楼主没说清楚。方程系数就是硬币面值，解就是硬币个数。等价于给一组硬币和总钱数
: ，求硬币组合。
|
b*****e
发帖数: 474 | 13 // my solution using recursion + global variables
int a[] = { 2, 3, 5, 7, 10 }; // sorted coin denominations
int size = 5; // number of coin types
int partial[MAX]; // store partial solutions (coins) -
// sorted in descending order
int partialSize=0; // partial solution size (# of coins)
void print_current_solution() {
for (int i=0; i
cout << endl;
return;
}
// do a DFS with partial solution stored in partial[]
void solve(int sum) {
for (int i=0; i
if ( a[i] > partial[partialSize] ) continue;
if ( sum >= a[i] ) {
partial[partialSize++] = a[i]; // extend the partial solution
if ( sum == a[i] ) print_current_solution();
else solve(sum-a[i]); // recurse down
partialSize--; // back up
}
}
}
【在 c*****e 的大作中提到】
: 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
: 次都只做了一道题，太慢了，看看别人都是好几道题。
|
c*****e
发帖数: 74 | 14 似乎coding style有些问题：
1. 数组partial[]没有initialize
2. 个人不喜欢Global variable用在这种情况,要不放到method里做参数，要不写成一
个class
3. 看了半天还是没明白思路，得到的结果有重复吗？要求是不能重复的。
【在 b*****e 的大作中提到】
: // my solution using recursion + global variables
: int a[] = { 2, 3, 5, 7, 10 }; // sorted coin denominations
: int size = 5; // number of coin types
: int partial[MAX]; // store partial solutions (coins) -
: // sorted in descending order
: int partialSize=0; // partial solution size (# of coins)
: void print_current_solution() {
: for (int i=0; i: cout << endl;
: return;
|
c*****e
发帖数: 74 | 15 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
次都只做了一道题，太慢了，看看别人都是好几道题。 |
l*********r
发帖数: 674 | 16 同问，分享一下方程的形式把。还从来没见过这种类型的面试题呢，应改不是单纯的做
数学题把，是不是有什么trick在里面。
【在 c*******t 的大作中提到】
: 是二次方程还是高次的？
|
c*****e
发帖数: 74 | 17 没有什么trick，就是解一个正正数系数方程，多元一次。不是数学题，是编程题。
【在 l*********r 的大作中提到】
: 同问，分享一下方程的形式把。还从来没见过这种类型的面试题呢，应改不是单纯的做
: 数学题把，是不是有什么trick在里面。
|
c*****e
发帖数: 74 | 18 多元一次。
【在 c*******t 的大作中提到】
: 是二次方程还是高次的？
|
L*******r
发帖数: 5448 | 19 多元一次不就是线性方程组吗
【在 c*****e 的大作中提到】
: 多元一次。
|
v***n
发帖数: 5085 | 20 LU decomposition? G-S? SD? |
|
|
g*********s
发帖数: 1782 | 21 正整数系数多元一次方程，求所有非负整数解？
这不就是print_all_coin_combination()吗？
【在 c*****e 的大作中提到】
: 没有什么trick，就是解一个正正数系数方程，多元一次。不是数学题，是编程题。
|
y****r
发帖数: 39 | |
x**y
发帖数: 70 | 23 数学题当场编程?
【在 c*****e 的大作中提到】
: 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
: 次都只做了一道题，太慢了，看看别人都是好几道题。
|
g*********s
发帖数: 1782 | 24 楼主没说清楚。方程系数就是硬币面值，解就是硬币个数。等价于给一组硬币和总钱数
，求硬币组合。
【在 y****r 的大作中提到】
: 飞思不可 转行做MATLAB了？
|
c*****e
发帖数: 74 | 25 是的是的，不好意思没说清楚。
【在 g*********s 的大作中提到】
: 楼主没说清楚。方程系数就是硬币面值，解就是硬币个数。等价于给一组硬币和总钱数
: ，求硬币组合。
|
b*****e
发帖数: 474 | 26 // my solution using recursion + global variables
int a[] = { 2, 3, 5, 7, 10 }; // sorted coin denominations
int size = 5; // number of coin types
int partial[MAX]; // store partial solutions (coins) -
// sorted in descending order
int partialSize=0; // partial solution size (# of coins)
void print_current_solution() {
for (int i=0; i
cout << endl;
return;
}
// do a DFS with partial solution stored in partial[]
void solve(int sum) {
for (int i=0; i
if ( a[i] > partial[partialSize] ) continue;
if ( sum >= a[i] ) {
partial[partialSize++] = a[i]; // extend the partial solution
if ( sum == a[i] ) print_current_solution();
else solve(sum-a[i]); // recurse down
partialSize--; // back up
}
}
}
【在 c*****e 的大作中提到】
: 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
: 次都只做了一道题，太慢了，看看别人都是好几道题。
|
c*****e
发帖数: 74 | 27 似乎coding style有些问题：
1. 数组partial[]没有initialize
2. 个人不喜欢Global variable用在这种情况,要不放到method里做参数，要不写成一
个class
3. 看了半天还是没明白思路，得到的结果有重复吗？要求是不能重复的。
【在 b*****e 的大作中提到】
: // my solution using recursion + global variables
: int a[] = { 2, 3, 5, 7, 10 }; // sorted coin denominations
: int size = 5; // number of coin types
: int partial[MAX]; // store partial solutions (coins) -
: // sorted in descending order
: int partialSize=0; // partial solution size (# of coins)
: void print_current_solution() {
: for (int i=0; i: cout << endl;
: return;
|
s*******f
发帖数: 1114 | 28 //get all integer positive solution for math function like 5x + 6y + z = 88;
//seems coefficient should be positive, otherwise, bruteforce?
void GetAllCombine_(int in[], int len, int sum, std::vector
> *out){
static std::vector v;
if (len < 1){
if (sum == 0){
out->push_back(v);
}
return;
}
for (int i = 0; i * in[0] <= sum; ++i){
v.push_back(i);
GetAllCombine_(in + 1, len - 1, sum - i * in[0], out);
v.pop_back();
}
}
void GetAllCombine(int in[], int len, int sum, std::vector
> *out){
if (!in || len < 1 || sum < 0 || !out)
return;
GetAllCombine_(in, len, sum, out);
}
【在 c*****e 的大作中提到】
: 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
: 次都只做了一道题，太慢了，看看别人都是好几道题。
|
f********e
发帖数: 166 | 29 我有一个傻逼的idea for 5x + 6y + z = 88
void getSolution(int a, int b, int c, int sum) //a=5,b=6,c=1
{
int numA = sum/a;
int numB = sum/b;
int numC = sum/c;
for(int i=0;i<=numA;++i)
for(int j =0;j<=numB;++j)
for(int k=0;k<=numC;++k)
if(x*i+y*j+z*k==88)
cout<
}
递归的方法还没想明白 |
c**********e
发帖数: 2007 | 30 This one is better: Only two loops, and the inner loop is shorter than yours.
void getSolution(int a, int b, int c, int sum) //a=5,b=6,c=1
{
int numA = sum/a;
for(int i=0;i<=numA;++i) {
int numB = (sum-a*i)/b;
for(int j=0;j<=numB;++j)
if((sum-a*i-b*j) % c == 0)
cout << i << j << (sum-a*i-b*j)/c << endl;
}
}
【在 f********e 的大作中提到】
: 我有一个傻逼的idea for 5x + 6y + z = 88
: void getSolution(int a, int b, int c, int sum) //a=5,b=6,c=1
: {
: int numA = sum/a;
: int numB = sum/b;
: int numC = sum/c;
: for(int i=0;i<=numA;++i)
: for(int j =0;j<=numB;++j)
: for(int k=0;k<=numC;++k)
: if(x*i+y*j+z*k==88)
|
|
|
s*****n
发帖数: 994 | 31 bool findSolution (int coefficient[], int size, int rightside){//coefficient
[i] for Xi.
if (size<1) return false;
int reviewed = new int[size];
int lreviewed = 0;
return findPartialSolution (reviewed,lreviewed, coefficient, size,
rightside);
}
bool findPartialSolution (int reviewed[], int lreviewed, int coefficient [],
int size, int rightside){
if (lreviewed==size){
for (int i=0;i
return;
}
bool found=false;
for (int i=0; i
lreviewed++;
reviewed[lreviewed-1] = i;
found ||= findPartialSolution (reviewed,lreviewed, coefficient, size,
rightside-i*coefficient[i]);
}
return found;
}
【在 c*****e 的大作中提到】
: 前面问了问background,然后一道题，求一个整系数方程的全部非负解，然后聊天。两
: 次都只做了一道题，太慢了，看看别人都是好几道题。
|
r*******g
发帖数: 1335 | |
B*******1
发帖数: 2454 | |
e***s
发帖数: 799 | 34 这个算传说中的brute force吗？
【在 f********e 的大作中提到】
: 我有一个傻逼的idea for 5x + 6y + z = 88
: void getSolution(int a, int b, int c, int sum) //a=5,b=6,c=1
: {
: int numA = sum/a;
: int numB = sum/b;
: int numC = sum/c;
: for(int i=0;i<=numA;++i)
: for(int j =0;j<=numB;++j)
: for(int k=0;k<=numC;++k)
: if(x*i+y*j+z*k==88)
|
