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]]
|
|