Pregunta sobre c# – construir una matriz de enteros para lograr una secuencia específica

2

construye la secuencia más corta posible de enteros que terminen con A, usando las siguientes reglas:

el primer elemento de la secuencia es 1, cada uno de los elementos sucesivos es la suma de cualquiera de los dos elementos anteriores (también se permite agregar un elemento único a sí mismo), cada elemento es más grande que todos los elementos anteriores; Es decir, la secuencia va en aumento.

Por ejemplo, para A = 42, una posible solución es [1, 2, 3, 6, 12, 24, 30, 42]. Otra posible solución es [1, 2, 4, 5, 8, 16, 21, 42].

He escrito lo siguiente pero falla en la entrada de 456, al devolver [1,2,4,8,16,32,64,128,200,256,456], no hay números en la secuencia que puedan sumarse para obtener 200.

¿Cómo puedo arreglar el siguiente código? ¿Qué estoy haciendo mal?

  public static int[] hit(int n)
    {
        List<int> nums = new List<int>();

        int x = 1;

        while (x < n)
        {
            nums.Add(x);
            x = x * 2;

            if (x > n)
            {

                    nums.Add(n - (x / 2));

                nums.Add(n);
            }
        }

        nums.Sort();
        int[] arr =  nums.ToArray();
        return arr;
    }
¿Cuál es tu pregunta? Oliver Charlesworth
@FarhadTaran - ¿ves lo que empezaste? Chris Gessler
@FarhadTaran - y ahora yo. ¡Gracias hombre! A ver si te invito a la cena de navidad ... :) Chris Gessler
Su algoritmo es simplemente incorrecto Desea algo recursivo para recorrer en iteración todas las secuencias posibles, romper las que pasan su número deseado y tomar la secuencia más corta. SimpleVar

Tu respuesta

5   la respuesta
1

pero supongo que sería mejor dividir el número entre 2, si se divide por igual, repita el proceso. Si hay un resto, sería 1. Así que tendría el cociente entero y el cociente más uno. Dado que se garantiza que uno está en el conjunto, el mayor de los 2 números ya está resuelto. Así que solo repite el proceso para los más pequeños. Este problema ciertamente implica una solución recursiva que debería ser relativamente trivial, por lo que dejaré eso en manos del cartel para implementarlo.

No es tan simple, por desgracia. Ese método daría[1,2,3,6,7,14,15] para 15, pero hay[1,2,3,6,12,15] una cadena más corta. Daniel Fischer
No, para 15 daría 15, 8, 7, 4, 3, 2, 1. Pero todavía estás en lo correcto. Estoy equivocado :) Lucas
0
public static int[] hit(int n)
    {
        List<int> nums = new List<int>();

        nums.Add(n);

        int x = 0;
        int Right = 0;
        int Left = 0;

        do
        {
            //even num
            if (n % 2 == 0)
            {
                x = n / 2;

                //result of division is also even 20/2 = 10 
                if (x % 2 == 0 || n>10 )
                {

                    nums.Add(x);

                    n = x;

                }
                else
                {
                    nums.Add(x + 1);
                    nums.Add(x - 1);

                    n = x - 1;
                }

            }
                //numbers that can only be divided by 3
            else if (n % 3 == 0)
            {
                x = n / 3;//46/3 =155

                 Right = x * 2;//155*2 = 310
                 Left = x;//155

                nums.Add(Right);
                nums.Add(Left);

                n = x;

            }
                //numbers that can only be divided by 5
            else
            {
                x = n / 2;
                Right = x + 1;
                Left = x;

                nums.Add(Right);
                nums.Add(Left);

                n = Left;
            }
        } while (n > 2);

        nums.Add(1);

        nums.Reverse();

        int[] arr = nums.ToArray();


        return arr;
    }
1

Creo que lo tengo:

public Set<Integer> shortList(int n){
    Set<Integer> result = new HashSet<Integer>();
    Stack<Integer> stack = new Stack<Integer>();
    result.add(n);
    int num=n, den=0;
    while(num>1){
        while(num > den){
            num--; den++;
            if(num%den==0)
                stack.push(num);
        }//num>den
        if(!stack.isEmpty()){
            num = stack.pop();
            result.add(num);
            stack.clear();
        }else{
            result.add(num);
            result.add(den);
        }
        den=0;
    }
    return result;
}//

Resultados (sin clasificar)

for 42: [1, 2, 3, 21, 6, 7, 42, 14]
for 15: [1, 2, 4, 5, 10, 15]
for 310: [1, 2, 155, 4, 5, 310, 10, 124, 62, 31, 15, 30]
Estoy mirando para ver cómo obtuvieron una respuesta más corta, todavía no la veo. Voy a seguir buscando. kasavbere
Tienes la misma longitud (13) para una entrada de 495 que yo, sin embargo, el sitio de prueba dice que es demasiado largo. ¿Algunas ideas? Ben Voigt
Finalmente encontré [1 2 4 8 16 32 33 66 99 198 396 495]. Sin embargo, otros números todavía resultan en secuencias no mínimas. Ben Voigt
0

private static IEnumerable<int> OptimalSequence(int lastElement)
{
    var result = new List<int>();
    int currentElement = 1;
    do
    {
        result.Add(currentElement);
        currentElement = currentElement * 2;
    } while (currentElement <= lastElement);
    var realLastElement = result.Last();
    if (lastElement != realLastElement)
    {
        result.Add(lastElement);                
        FixCollection(result, lastElement - realLastElement);
    }
    return result;
}

private static void FixCollection(List<int> result, int difference)
{
    for (int i = 0; i < result.Count; i++)
    {
        if (result[i] == difference) break;
        if (result[i] > difference)
        {
            result.Insert(i, difference);
            FixCollection(result, difference - result[i-1]);
            break;
        }
    }
}

Editar No puedo demostrarlo formalmente, pero mi respuesta y la respuesta de Chris Gessler dan secuencias del mismo tamaño (al menos revisé los números entre 1 y 10000) porque ambos algoritmos compensan los números impares. Algunos ejemplos:

Number 1535
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1024,1535
Number 2047
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047
Number 3071
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2048,3071
Number 4095
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4095
Number 6143
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4096,6143
Number 8191
1,2,3,4,7,8,15,16,31,32,63,64,127,128,255,256,511,512,1023,1024,2047,2048,4095,4096,8191

==============

Number 1535
1,2,4,5,10,11,22,23,46,47,94,95,190,191,382,383,766,767,1534,1535
Number 2047
1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047
Number 3071
1,2,4,5,10,11,22,23,46,47,94,95,190,191,382,383,766,767,1534,1535,3070,3071
Number 4095
1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047,4094,4095
Number 6143
1,2,4,5,10,11,22,23,46,47,94,95,190,191,382,383,766,767,1534,1535,3070,3071,6142,6143
Number 8191
1,2,3,6,7,14,15,30,31,62,63,126,127,254,255,510,511,1022,1023,2046,2047,4094,4095,8190,8191
Disculpe, tiene razón, pero sigue fallando, ¿pueden eliminarse 54? Creo que su 54 lo hace fallar. user1362208
esto es muy bueno, pero aún falla con una entrada de 310, el objetivo es llegar a la secuencia más corta, 310 da, {1,2,4,6,8,16,22,32,54,64,128,256,310} , 2 + 6 = 8, y 4 + 4 = 8, por lo que 6 se pueden eliminar aquí. user1362208
64 + 64 = 128, se permite agregar un número a sí mismo. user1362208
Lo siento, 54 es para 310 = 256 + 54 empi
1

void printSequenceTo(unsigned n)
{
    if (n == 1) { printf("1"); return; }
    if (n & 1) {
        int factor = 3;
        do {
            if (n % factor == 0) {
                printSequenceTo(n / factor * (factor-1));
                factor = 0;
                break;
            }
            factor += 2;
        } while (factor * factor <= n);
        if (factor) printSequenceTo(n-1);
    }
    else
        printSequenceTo(n/2);
    printf(",%u", n);
}

Demostración:http://ideone.com/8lXxc

Naturalmente, podría acelerarse utilizando un tamiz para la factorización.

Tenga en cuenta que esta es una mejora significativa sobre la respuesta aceptada, pero aún no es óptima.

asi quepor qué ¿Funciona este algoritmo? BrokenGlass
[1 2 4 8 16 32 33 66 99 198 396 495] parece una secuencia más corta, ¿ahora cómo obtenerla? Ben Voigt
@BrokenGlass: desafortunadamente no es mínimo. Factoriza el número en números primos y produce una secuencia de pasos para cada factor (multiplicado por todos los factores anteriores). Entonces, por ejemplo, 35 = 5 * 7, obtiene [1 2 4 5] y [1 2 4 6 7] * 5 combinados en [1 2 4 5 10 20 30 35]. Creo que tal vez debería tener en cuenta (2 ** n + 1), ya que mi salida actual para 1025 es muy mala. Ben Voigt
Creo que esto podría ser:ideone.com/vrgfd Ben Voigt

Preguntas relacionadas