h******8
发帖数: 55 | 1 1. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
2. implement adding two unsigned numbers without using "+"
3. implement sqrt
多谢 |
j*****u
发帖数: 1133 | 2 1. 除了2^N外的数都可以
2. a+b = (a XOR b) + (a AND b)<<1，递归
3. binary search, sqrt(n): min=1, max=n,循环计算mid^2直到它接近n
【在 h******8 的大作中提到】
: 1. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 2. implement adding two unsigned numbers without using "+"
: 3. implement sqrt
: 多谢
|
g*****k
发帖数: 623 | 3 n=k*m+(k-1)*k/2, 2<=k
【在 h******8 的大作中提到】
: 1. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 2. implement adding two unsigned numbers without using "+"
: 3. implement sqrt
: 多谢
|
g*****k
发帖数: 623 | 4
This is interesting. How to prove it?
It seems it is easy to show the prime case.
【在 j*****u 的大作中提到】
: 1. 除了2^N外的数都可以
: 2. a+b = (a XOR b) + (a AND b)<<1，递归
: 3. binary search, sqrt(n): min=1, max=n,循环计算mid^2直到它接近n
|
g*****k
发帖数: 623 | 5 all right, I got the proof.
yeah, only 2^m cannot be expressed as a sum of k consequtive integers.
【在 g*****k 的大作中提到】
:
: This is interesting. How to prove it?
: It seems it is easy to show the prime case.
|
s*******e
发帖数: 93 | 6 For 3 you can use Newton–Raphson method to solve x^2=n and get a more exact
answer. |
x*****p
发帖数: 1707 | 7 It is not correct.
Here is simple example, n = 10, k = 3, then n can not be expressed as
the sum of 3 consecutive integers.
Here is the solution.
Suppose n = m + (m+1) + ... + (m+k-1) = km + k(k-1)/2
We only need to calculate n - k(k-1)/2 and check if it is a multiple of
k.
However, the problem can have another meaning. That is, k is not given
and can be any positive integer. then only 2^m can not be expressed as a
sum of k consecutive integers for any given k>1.
Here is a proof. If n is odd, then n = 2m+1 = m + (m+1). If n is even
but not 2^m, then n = 2^t * r, where r is odd. Let r = 2s + 1, then we
have
n = (2^t - s) + (2^t - s + 1) + ... + (2^t) + (2^t + 1) + ... + (2^t +
s).
【在 g*****k 的大作中提到】
: all right, I got the proof.
: yeah, only 2^m cannot be expressed as a sum of k consequtive integers.
|
g*****k
发帖数: 623 | 8 k can be any number >=2.
so for n=10, it can be expressed as 1234.
【在 x*****p 的大作中提到】
: It is not correct.
: Here is simple example, n = 10, k = 3, then n can not be expressed as
: the sum of 3 consecutive integers.
: Here is the solution.
: Suppose n = m + (m+1) + ... + (m+k-1) = km + k(k-1)/2
: We only need to calculate n - k(k-1)/2 and check if it is a multiple of
: k.
: However, the problem can have another meaning. That is, k is not given
: and can be any positive integer. then only 2^m can not be expressed as a
: sum of k consecutive integers for any given k>1.
|
g*********s
发帖数: 1782 | 9
if and only if there exists m >= 0 and n > 0 such that t = 2^m*(2n+1)?
just follow the hardware implementation of int adder.
numeric method. use binary search or newton?
【在 h******8 的大作中提到】
: 1. 设计一个算法，判断一个integer n是不是可以表示成k(k>=2)个连续正整数的和
: 2. implement adding two unsigned numbers without using "+"
: 3. implement sqrt
: 多谢
|
g*********s
发帖数: 1782 | 10
u still use "+".
【在 j*****u 的大作中提到】
: 1. 除了2^N外的数都可以
: 2. a+b = (a XOR b) + (a AND b)<<1，递归
: 3. binary search, sqrt(n): min=1, max=n,循环计算mid^2直到它接近n
|
|
|
C*****n
发帖数: 1872 | 11 (a&b)<<1 will reach 0 through iteration or recursion, which means a^b is the
sum
【在 g*********s 的大作中提到】
:
: u still use "+".
|
J*********r
发帖数: 5921 | 12 I think what he actually meant is like below since he mentioned recursion.
unsigned add(unsigned a, unsigned b){
if(b==0)
return a;
return add(a^b, (a&b)<<1);
}
(a&b)<<1 stores the carries and will be ultimately left-shifted out of all
bits, leaving a 0, which is the base case here.
【在 g*********s 的大作中提到】
:
: u still use "+".
|
J*********r
发帖数: 5921 | 13 zan, I considered both cases too...got a little confused at first, but I
think the 2nd one should be the intended case.
【在 x*****p 的大作中提到】
: It is not correct.
: Here is simple example, n = 10, k = 3, then n can not be expressed as
: the sum of 3 consecutive integers.
: Here is the solution.
: Suppose n = m + (m+1) + ... + (m+k-1) = km + k(k-1)/2
: We only need to calculate n - k(k-1)/2 and check if it is a multiple of
: k.
: However, the problem can have another meaning. That is, k is not given
: and can be any positive integer. then only 2^m can not be expressed as a
: sum of k consecutive integers for any given k>1.
|
g*********s
发帖数: 1782 | 14 yes, this is much more clear.
recursion.
all
【在 J*********r 的大作中提到】
: I think what he actually meant is like below since he mentioned recursion.
: unsigned add(unsigned a, unsigned b){
: if(b==0)
: return a;
: return add(a^b, (a&b)<<1);
: }
: (a&b)<<1 stores the carries and will be ultimately left-shifted out of all
: bits, leaving a 0, which is the base case here.
|
B********n
发帖数: 384 | 15 This is good but not accurate proof. All numbers are supposed to be positibe
, that is not the case in your proof.
n = (2^t - s) + (2^t - s + 1) + ... + (2^t) + (2^t + 1) + ... + (2^t +
s).
【在 x*****p 的大作中提到】
: It is not correct.
: Here is simple example, n = 10, k = 3, then n can not be expressed as
: the sum of 3 consecutive integers.
: Here is the solution.
: Suppose n = m + (m+1) + ... + (m+k-1) = km + k(k-1)/2
: We only need to calculate n - k(k-1)/2 and check if it is a multiple of
: k.
: However, the problem can have another meaning. That is, k is not given
: and can be any positive integer. then only 2^m can not be expressed as a
: sum of k consecutive integers for any given k>1.
|
l*********r
发帖数: 674 | 16 这种鸟题如果事先没看过，面试问到了还真是眼前一黑阿。
有没有什么解这类题的general的idea么？
【在 J*********r 的大作中提到】
: I think what he actually meant is like below since he mentioned recursion.
: unsigned add(unsigned a, unsigned b){
: if(b==0)
: return a;
: return add(a^b, (a&b)<<1);
: }
: (a&b)<<1 stores the carries and will be ultimately left-shifted out of all
: bits, leaving a 0, which is the base case here.
|
g*********s
发帖数: 1782 | 17 you may not be asked to write the code in 5 minutes. but you definitely
need to know how the addition is implemented by bit operation, as this is
the basic concepts in an entry level computer hardware course like cs 101.
【在 l*********r 的大作中提到】
: 这种鸟题如果事先没看过，面试问到了还真是眼前一黑阿。
: 有没有什么解这类题的general的idea么？
|
