w*****e
发帖数: 158 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: woommle (mm), 信区: JobHunting
标 题: 两道算法题
发信站: BBS 未名空间站 (Mon Sep 27 16:56:25 2010, 美东)
1) given the whole range of 6 digit numbers, design an algorithm which
prints out numbers which have the sum of the right 3 digits equal the left
3 digits? like 123600, 345435 etc.
2）design an algorithm to find square_root of a float? how do you make the
algorithm efficient?
第一题：除了每个数检验之外，还有什么更快得方法吗？
第二题：貌似可以用bisection method 或者 Newton method， Newton method 收敛的
更快
一些。有什么地方需要注意或者 | k*******d
发帖数: 1340 | 2 第一个问题是从100000-999999中吗？那么应该不需要每个查过去，前三位从100-999穷
举，对每一个前三位，给定了数字和，穷举出所有可能的后三位，前后拼起来就可以了。
具体做起来我想可以这样，
for i = 1 - 999
array[i] = 三位数字的和。
建立一个数组，size 27，每个元素是一个链表，每个链表里面的三位数数字和是一样的
for i = 0 - 999
linkedlist[array[i]].append(i).
for i = 100 to 999
for j in linkedlist[array[i]]
i 和 j 拼起来就是想要的
时间空间都是O(1000)，可能空间用大了一些 | z****g
发帖数: 1978 | 3 1) Dynamic programming
2) You are right about traditional method. But for a really fast and dirty
way, check the math class for Quake, which uses a 'Misery' constant to
bitwise shift the original value. | z****g
发帖数: 1978 | 4 Sorry, 1) is wrong, I thought you are given 6 digits and asked to figure
out all the valid numbers.
dirty
【在 z****g 的大作中提到】
: 1) Dynamic programming
: 2) You are right about traditional method. But for a really fast and dirty
: way, check the math class for Quake, which uses a 'Misery' constant to
: bitwise shift the original value.
| b********u
发帖数: 63 | 5 1)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
for (int a = 1; a <= 9; ++a)
{
for (int b = 0; b <= 9; ++b)
{
for (int c = 0; c <= 9; ++c)
{
for (int d = MAX(a+b+c-18,0); d <= MIN(9, a+b+c); ++d)
{
for (int e = MAX(a+b+c-d-9,0); e <= MIN(9, a+b+c-d); ++e)
{
int f = a+b+c-d-e;
assert(f >= 0 && f <= 9);
cout << a << b << c << d << e << f << endl;
}
}
}
}
}
【在 w*****e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: woommle (mm), 信区: JobHunting
: 标 题: 两道算法题
: 发信站: BBS 未名空间站 (Mon Sep 27 16:56:25 2010, 美东)
: 1) given the whole range of 6 digit numbers, design an algorithm which
: prints out numbers which have the sum of the right 3 digits equal the left
: 3 digits? like 123600, 345435 etc.
: 2）design an algorithm to find square_root of a float? how do you make the
: algorithm efficient?
: 第一题：除了每个数检验之外，还有什么更快得方法吗？
| w*****e
发帖数: 158 | 6 Nice, this is very nice idea. Thank you.
Like the hashtable with chaining.
了。
样的
【在 k*******d 的大作中提到】
: 第一个问题是从100000-999999中吗？那么应该不需要每个查过去，前三位从100-999穷
: 举，对每一个前三位，给定了数字和，穷举出所有可能的后三位，前后拼起来就可以了。
: 具体做起来我想可以这样，
: for i = 1 - 999
: array[i] = 三位数字的和。
: 建立一个数组，size 27，每个元素是一个链表，每个链表里面的三位数数字和是一样的
: for i = 0 - 999
: linkedlist[array[i]].append(i).
: for i = 100 to 999
: for j in linkedlist[array[i]]
|
|
