Pytanie w sprawie c# – skonstruuj tablicę liczb całkowitych, aby uzyskać określoną sekwencję

2

skonstruuj najkrótszą możliwą sekwencję liczb całkowitych kończącą się literą A, stosując następujące reguły:

pierwszym elementem sekwencji jest 1, każdy z kolejnych elementów jest sumą dwóch poprzednich elementów (dodanie pojedynczego elementu do siebie jest również dopuszczalne), każdy element jest większy niż wszystkie poprzednie elementy; to znaczy sekwencja wzrasta.

Na przykład dla A = 42 możliwe rozwiązania to [1, 2, 3, 6, 12, 24, 30, 42]. Innym możliwym rozwiązaniem jest [1, 2, 4, 5, 8, 16, 21, 42].

Napisałem następujące, ale nie powiedzie się na wejściu 456, zwracając [1,2,4,8,16,32,64,128,200,256,456], nie ma żadnych numerów w sekwencji, które można by dodać do 200.

jak mogę naprawić poniższy kod? Co ja robię źle?

  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;
    }
To, co chcesz, nazywa się (minimalnym)łańcuch dodatkowy. Znajdowanie minimalnego łańcucha dodawaniato trudny problem, przynajmniej jeśli wydajność odgrywa rolę. Także @ ChrisGessler. Daniel Fischer
@ FarhadTaran - czy widzisz, co zacząłeś? Chris Gessler
@ FarhadTaran - a teraz ja. Dzięki! Zobacz, czy zapraszam na świąteczny obiad ... :) Chris Gessler
@FarhadTaran: Jakie debugowanie zrobiłeś do tej pory? Oliver Charlesworth

Twoja odpowiedź

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

Demonstracja:http://ideone.com/8lXxc

Naturalnie można go przyspieszyć za pomocą sita do faktoryzacji.

Należy zauważyć, że jest to znacząca poprawa w stosunku do zaakceptowanej odpowiedzi, ale nadal nie jest optymalna.

@BrokenGlass: Niestety nie jest minimalny. Określa liczbę w liczbach pierwszych i tworzy sekwencję kroków dla każdego czynnika (pomnożoną przez wszystkie wcześniejsze czynniki). Tak więc powiedzmy 35 = 5 * 7, otrzymuje [1 2 4 5] i [1 2 4 6 7] * 5 połączone w [1 2 4 5 10 20 30 35]. Myślę, że zamiast tego powinienem brać pod uwagę (2 ** n + 1), ponieważ moje bieżące wyjście dla 1025 jest bardzo złe. Ben Voigt
Myślę, że to może być to:ideone.com/vrgfd Ben Voigt
Nie, wciąż odrzucony. Ben Voigt
[1 2 4 8 16 32 33 66 99 198 396 495] wygląda jak najkrótsza sekwencja, teraz jak ją zdobyć? Ben Voigt
1

że za tym kryje się dowód matematyczny, ale przypuszczam, że będzie to dzielenie liczby przez 2, jeśli dzieli się równomiernie, powtórz proces. Gdyby istniała reszta, byłaby to 1. Więc miałbyś iloraz całkowity i iloraz plus jeden. Ponieważ jeden jest zagwarantowany w zestawie, większa z 2 liczb jest już zajęta. Po prostu powtórz proces dla mniejszych. Problem ten z pewnością pociąga za sobą rekurencyjne rozwiązanie, które powinno być stosunkowo trywialne, więc zostawiam to plakatowi do wdrożenia.

Nie, dla 15 dawałoby 15, 8, 7, 4, 3, 2, 1. Ale wciąż masz rację. Jestem w błędzie :) Lucas
Niestety nie jest to takie proste. Ta metoda dałaby[1,2,3,6,7,14,15] za 15, ale jest[1,2,3,6,12,15] krótszy łańcuch. Daniel Fischer
1

Myślę, że rozumiem:

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

Wyniki (nieposortowane)

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]
Chcę zobaczyć, jak otrzymali krótszą odpowiedź, jeszcze tego nie widzę. Będę dalej szukać. kasavbere
W końcu znalazłem [1 2 4 8 16 32 33 66 99 198 396 495]. Jednak inne liczby nadal dają sekwencje nie minimalne. Ben Voigt
Masz taką samą długość (13) dla wejścia 495 jak ja, ale strona testowa mówi, że to za długo. Jakieś pomysły? Ben Voigt
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;
    }
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;
        }
    }
}

Edytować Formalnie nie mogę tego udowodnić, ale moja odpowiedź i odpowiedź Chrisa Gesslera dają sekwencje o tym samym rozmiarze (przynajmniej sprawdziłem liczby od 1 do 10000), ponieważ oba algorytmy kompensują liczby nieparzyste. Kilka przykładów:

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
6 nie można usunąć, ponieważ jest to konieczne dla 22. empi
jest to bardzo dobre, ale nadal kończy się niepowodzeniem z wejściem 310, celem jest wymyślenie najkrótszej sekwencji, 310 daje, {1,2,4,6,8,16,22,32,54,64,128,256,310} , 2 + 6 = 8 i 4 + 4 = 8, więc 6 tutaj można usunąć. user1362208
64 + 64 = 128, dodawanie liczby do siebie jest dopuszczalne. user1362208
Przepraszamy, 54 oznacza 310 = 256 + 54 empi

Powiązane pytania