porcentaje - numero de filas y columnas de numbers
formar un número usando números consecutivos (5)
Me quedé desconcertado con una de las preguntas en la entrevista de Microsoft, que es la siguiente:
Una función debe aceptar un rango (3 - 21) y debe imprimir todas las combinaciones de números consecutivos para formar cada número como se indica a continuación:
3 = 1+2 5 = 2+3 6 = 1+2+3 7 = 3+4 9 = 4+5 10 = 1+2+3+4 11 = 5+6 12 = 3+4+5 13 = 6+7 14 = 2+3+4+5 15 = 1+2+3+4+5 17 = 8+9 18 = 5+6+7 19 = 9+10 20 = 2+3+4+5+6 21 = 10+11 21 = 1+2+3+4+5+6
¿Podrías por favor ayudarme a formar esta secuencia en C #?
Gracias, Mahesh
Así que aquí hay una respuesta directa / ingenua (en C ++, y no probada, pero debería ser capaz de traducir). Utiliza el hecho de que
1 + 2 + ... + n = n (n + 1) / 2,
que probablemente has visto antes Hay muchas optimizaciones fáciles que se pueden hacer aquí que he omitido para mayor claridad.
void WriteAsSums (int n)
{
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
if (n = (j * (j+1) - i * (i+1))/2) // then n = (i+1) + (i+2) + ... + (j-1) + j
{
std::cout << n << " = ";
for (int k = i + 1; k <= j; k++)
{
std::cout << k;
if (k != j) // this is not the interesting bit
std::cout << std::endl;
else
std::cout << " + ";
}
}
}
}
}
Aquí hay algo en Groovy, debería ser capaz de entender lo que está pasando. No es el código más eficiente y no crea las respuestas en el orden que usted cita en su pregunta (sin embargo, parece que le faltan algunas) pero podría darle un comienzo.
def f(a,b) {
for (i in a..b) {
for (j in 1..i/2) {
def (sum, str, k) = [ 0, "", j ]
while (sum < i) {
sum += k
str += "+$k"
k++
}
if (sum == i) println "$i=${str[1..-1]}"
}
}
}
La salida para f(3,21)
es:
3=1+2
5=2+3
6=1+2+3
7=3+4
9=2+3+4
9=4+5
10=1+2+3+4
11=5+6
12=3+4+5
13=6+7
14=2+3+4+5
15=1+2+3+4+5
15=4+5+6
15=7+8
17=8+9
18=3+4+5+6
18=5+6+7
19=9+10
20=2+3+4+5+6
21=1+2+3+4+5+6
21=6+7+8
21=10+11
Espero que esto ayude. De alguna manera se ajusta al principio de hacer lo más simple que pueda funcionar.
Este es un pseudo código para encontrar todas las combinaciones, si las hay:
function consecutive_numbers(n, m)
list = [] // empty list
list.push_back(m)
while m != n
if m > n
first = list.remove_first
m -= first
else
last = list.last_element
if last <= 1
return []
end
list.push_back(last - 1)
m += last - 1
end
end
return list
end
function all_consecutive_numbers(n)
m = n / 2 + 1
a = consecutive_numbers(n, m)
while a != []
print_combination(n, a)
m = a.first - 1
a = consecutive_numbers(n, m)
end
end
function print_combination(n, a)
print(n + " = ")
print(a.remove_first)
foreach element in a
print(" + " + element)
end
print("/n")
end
Se imprimiría una llamada a all_consecutive_numbers (21):
21 = 11 + 10
21 = 8 + 7 + 6
21 = 6 + 5 + 4 + 3 + 2 + 1
Lo probé en ruby (código aquí ) y parece funcionar. Estoy seguro de que la idea básica también podría implementarse fácilmente en C #.
Me gusta este problema Aquí hay una solución O (n) lisa y ligeramente misteriosa:
void DisplaySum (int n, int a, int b)
{
std::cout << n << " = ";
for (int i = a; i < b; i++) std::cout << i << " + ";
std::cout << b;
}
void WriteAsSums (int n)
{
N = 2*n;
for (int i = 1; i < N; i++)
{
if (~(N%i))
{
int j = N/i;
if (j+i%2)
{
int a = (j+i-1)/2;
int b = (j-i+1)/2;
if (a>0 & a<b) // exclude trivial & negative solutions
DisplaySum(n,a,b);
}
}
}
}
si rebanamos a en 2 dígitos, entonces a = b + (b + 1) = 2 * b + (0 + 1)
si rebanamos a en 3 dígitos, entonces a = b + (b + 1) + (b + 2) = 3 * b + (0 + 1 + 2)
...
si cortamos a n dígito, entonces a = b + (b + 1) + ... + (b + n) = n b + (0 + 1 + n-1)
el último resultado es a = n b + n * (n-1) / 2, a, b, n son todas las entradas.
entonces O (N) Algoritmo es:
void seq_sum(int a)
{
// start from 2 digits
int n=2;
while(1)
{
int value = a-n*(n-1)/2;
if(value < 0)
break;
// meet the quotation we deduct
if( value%n == 0 )
{
int b=value/n;
// omit the print stage
print("......");
}
n++;
}
}