Алгоритм псевдокода / Java Mystery

Question

У меня есть алгоритм, и я хочу понять, что он делает. Я уверен, что некоторые из вас могут просто посмотреть на это и сказать мне, что он делает, но я смотрел на это в течение получаса, и я все еще не уверен. Просто становится грязно, когда я пытаюсь поиграть с ним. Каковы ваши методы разрушения такого алгоритма? Как мне проанализировать подобные вещи и узнать, что происходит?

Я предполагаю, что это сортировка чисел от наименьшего к большему, но я не слишком уверен.

1. mystery(a1 , a2 , . . . an : array of real numbers)
    2. k = 1
    3. bk = a1
    4. for i = 2 to n
        5. c = 0
        6. for j = 1 to i − 1
            7. c = aj + c
        8. if (ai ≥ c)
            9. k = k + 1
           10. bk = ai
    11. return b1 , b2 , . . . , bk

Вот эквивалент, который я пытался написать на Java, но я не уверен, правильно ли я перевел:

public int[] foo(int[] a) {
        int k=1;
        int nSize=10;
        int[] b=new int[nSize];
        b[k]=a[1];
        for (int i=2;i<a.length;){
            int c=0;
            for (int j=1;j<i-1;)
                c=a[j]+c;
            if (a[i]>=c){
                k=k+1;
                b[k]=a[i];

Answer 1

Google не перестает удивлять, из-за 29го я так понимаю? ;)

Перевод на Java - хорошая идея, после того, как вы приступите к работе, вы сможете просмотреть его, чтобы точно узнать, что делает алгоритм, если у вас возникают проблемы с его визуализацией.

Несколько указателей: код psuedo имеет индексированные массивы от 1 до n, массивы Java индексируются от 0 до length - 1. Ваши петли должны быть изменены, чтобы соответствовать этому. Также вы оставили приращения на своих циклах - i++, j++.

Создание b магического константного размера также не является хорошей идеей - если посмотреть на псевдокод, мы видим, что он записан не более n - 1 раз, так что это будет хорошей отправной точкой для его размера. Вы можете изменить его размер, чтобы он подходил к концу.

Окончательный совет, время алгоритма O (n ² ). Это легко определить - внешний для цикла выполняется n раз, внутренний для цикла n / 2 раза, для общего времени выполнения (n * (n / 2)). Доминирует n * n, что и касается Big O, что делает его алгоритмом O (n ² ).

Answer 2

Самый простой способ - взять образец, но небольшой набор цифр, и обработать его на бумаге.В вашем случае возьмем число a[] = {3,6,1,19,2}.Теперь нам нужно пройтись по вашему алгоритму:

Инициализация:

i = 2
b[1] = 3

После итерации 1:

i = 3
b[2] = 6

После итерации 2:

i = 4
b[2] = 6

После итерации 3:

i = 5
b[3] = 19

После итерации 4:

i = 6
b[3] = 19

Результат b[] = {3,6,19}

Вероятно, вы можете догадаться, что он делает.

Answer 3

Ваш код довольно близок к псевдокоду, но есть несколько ошибок:

• В ваших for циклах отсутствуют правила приращения: i++, j++
• Java-массивы основаны на 0, а не на 1, поэтому вы должны инициализировать k=0, a[0], i=1, e.t.c.

Кроме того, это не сортировка, а фильтрация - вы получаете несколько элементов, но в том же порядке.

Answer 4

При преобразовании в java, будьте осторожны с индексами массива, так как этот псевдокод, по-видимому, подразумевает индекс на основе 1.

Из статического анализа:

• a является входным значением ине изменяется
• b - это вывод
• k, по-видимому, является указателем на элемент b, который будет увеличиваться только при определенных обстоятельствах (поэтому мы можем думать о k = k+1 как о значении«в следующий раз, когда мы напишем в b, мы напишем в следующий элемент»)
• что делает цикл в строках 6-7?Итак, каково значение c?
• , используя тогда предыдущий ответ, когда строка 8 верна?
• , поскольку строки 9-10 выполняются только тогда, когда строка 8 истинна, что это говорит оэлементы в выводе?

Тогда вы можете приступить к здравому смыслу, проверьте свой ответ:

• будут ли установлены все элементы вывода?
• попробуйте запустить psuedocode с вводом, подобным [1,2,3,4] - что вы ожидаете получить?

Answer 5

Как мне проанализировать подобные вещи и узнать, что происходит?

Основная техника для чего-то подобного - это выполнить это вручную карандашом и бумагой.

Более продвинутый метод состоит в том, чтобы разбить код на части, выяснить, что делают части, а затем мысленно собрать его.(Хитрость заключается в выборе границ для разложения. Это требует практики.)

Как только вы в этом разберетесь, вы начнете «читать» псевдокод ... хотя этот пример, вероятно,немного грубовато для большинства кодеров, чтобы справиться с этим.

Answer 6

def funct(*a)
  sum = 0
  a.select {|el| (el >= sum).tap { sum += el }}
end

Srsly? Кто придумывает эти домашние вопросы?

Кстати: поскольку здесь одновременно выполняются и scan, и filter, а filter зависит от scan, язык которого обладает необходимыми функциями для краткого выражения этого так, что последовательность пройдена только один раз?