Pergunta sobre c# – construir uma matriz de inteiros para alcançar uma seqüência específica

2

construir a seqüência mais curta possível de inteiros terminando com A, usando as seguintes regras:

o primeiro elemento da seqüência é 1, cada um dos elementos sucessivos é a soma de quaisquer dois elementos anteriores (adicionar um único elemento a si mesmo também é permitido), cada elemento é maior que todos os elementos anteriores; isto é, a sequência está aumentando.

Por exemplo, para A = 42, uma solução possível é [1, 2, 3, 6, 12, 24, 30, 42]. Outra solução possível é [1, 2, 4, 5, 8, 16, 21, 42].

Eu escrevi o seguinte, mas ele falha na entrada de 456, retornando [1,2,4,8,16,32,64,128,200,256,456], não há números na seqüência que podem ser somados para obter 200.

Como posso corrigir o código abaixo? O que estou fazendo de errado?

  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;
    }
"O que estou fazendo de errado?" Por um lado, você nem mesmo verifica se algum dos números pode ser obtido adicionando dois dos anteriores. Daniel Fischer
@ FarhadTaran - e agora eu. Obrigado cara! Veja se eu te convido para o jantar de Natal ... :) Chris Gessler
@ FarhadTaran: Que depuração você fez até agora? Oliver Charlesworth
Qual é a sua pergunta? Oliver Charlesworth

Sua resposta

5   a resposta
1

Eu sei que vai haver uma prova matemática por trás disso, mas meu palpite seria ao longo das linhas de dividir o número por 2, se dividir igualmente, repita o processo. Se houver um resto, seria 1. Então você teria o quociente inteiro e o quociente mais um. Como é garantido que um está no set, o maior dos dois números já está resolvido. Então, basta repetir o processo para o menor. Esse problema certamente implica uma solução recursiva que deve ser relativamente trivial, então deixarei isso para o cartaz para implementar.

Não é tão simples, infelizmente. Esse método daria[1,2,3,6,7,14,15] por 15, mas há[1,2,3,6,12,15] uma corrente mais curta. Daniel Fischer
Não, por 15 daria 15, 8, 7, 4, 3, 2, 1. Mas você ainda está correto. Eu estou errado :) 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

Eu acho que entendi:

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 (não classificados)

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]
Eu finalmente encontrei [1 2 4 8 16 32 33 66 99 198 396 495]. No entanto, outros números ainda resultam em sequências não mínimas. Ben Voigt
Você tem o mesmo comprimento (13) para uma entrada de 495 como eu fiz, no entanto, o site de testes diz que é muito longo. Alguma ideia? Ben Voigt
Eu estou olhando para ver como eles têm uma resposta mais curta, eu não estou vendo ainda. Eu continuarei procurando. kasavbere
0

Aqui está minha tentativa. Pode ser otimizado, mas mostra minha ideia:

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 Eu não posso provar isso formalmente, mas minha resposta e a resposta de Chris Gessler dão sequências do mesmo tamanho (pelo menos eu verifiquei números entre 1 e 10000) porque ambos os algoritmos compensam números ímpares. Alguns exemplos:

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
54 é necessário para 128 empi
desculpe, você está certo, mas ainda falha, pode ser removido? Eu acho que é 54 que faz falhar. user1362208
Desculpe, 54 é para 310 = 256 + 54 empi
isso é muito bom, mas ainda falha com uma entrada de 310, o objetivo é chegar à sequência mais curta, 310 dá, {1,2,4,6,8,16,22,32,54,64,128,256,310} , 2 + 6 = 8 e 4 + 4 = 8, então 6 aqui podem ser removidos. user1362208
1

Aqui está a minha solução em C ++ (pode ser modificada para C #):

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);
}

Demonstração:http://ideone.com/8lXxc

Naturalmente, poderia ser acelerado usando uma peneira para fatoração.

Note que isso é uma melhoria significativa em relação à resposta aceita, mas ainda não é o ideal.

@BrokenGlass: Não é mínimo, infelizmente. Ele fatora o número em primos e produz uma seqüência de etapas para cada fator (multiplicado por todos os fatores anteriores). Portanto, para dizer 35 = 5 * 7, ele obtém [1 2 4 5] e [1 2 4 6 7] * 5 combinados em [1 2 4 5 10 20 30 35]. Eu acho que talvez eu deva estar fatorando em (2 ** n + 1), pois minha saída atual para 1025 é muito ruim. Ben Voigt
[1 2 4 8 16 32 33 66 99 198 396 495] parece uma seqüência mais curta, agora como obtê-lo? Ben Voigt
Eu acho que isso pode ser isso:ideone.com/vrgfd Ben Voigt
assimporque este algoritmo funciona? BrokenGlass

Perguntas relacionadas