Как вывести простые числа в порядке убывания, используя стек? - PullRequest
Новая
       16

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

1 голос
/ 15 февраля 2011 
import java.util.Stack;

public class Primes{
    public static void main(String[]args){
    Stack<Integer> stack = new Stack<Integer>();

    stack.push(null);
    //number of primes to display
    final int NUMBER_OF_PRIMES = 50;
    //number of primes to display per line
    final int NUMBER_OF_PRIMES_PER_LINE = 10;
    //count number of primes
    int count = 0;
    int number = 2;

    System.out.println("The first 50 primes are \n");

    while(count < NUMBER_OF_PRIMES){
        boolean isPrime = true;

    for(int divisor = 2; divisor <= number/2; divisor++){
        if(number % divisor == 0){
            isPrime = false;
            break;
        }
    }
    if(isPrime){
        count++;

        if(count % NUMBER_OF_PRIMES_PER_LINE ==0){
            System.out.println(number);

        }
        else
            System.out.print(number + " ");

    }
    number++;
    }
}
}

Ответы [ 4 ]

0 голосов
/ 15 февраля 2011

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

Представьте себе, если я помещу буквы слова «панорамирование» в стек, одну за другой.Сначала я нажимаю «p», затем «a», затем «n».Теперь, так как «n» была последней нажатой буквой, это первая буква, которая будет вытолкнута из стека.Таким образом, когда я удаляю буквы, я получаю «n», затем «a» и «p» - «nap».Таким образом, стек может использоваться для обращения слова назад, рассматривая его как список символов.

То же самое верно для списка простых чисел.Если у вас есть список первых NUMBER_OF_PRIMES простых чисел в порядке возрастания (например, 2, 3, 5, 7 ...), то вы можете выполнить тот же трюк, используя стек, чтобы изменить этот список на по убыванию упорядочьте, поместив каждый в стек, а затем считав их.

Итак, что бы я делал, каждый раз, когда вы обнаруживаете простое число, помещайте его в свой стек до тех пор, пока не будет NUMBER_OF_PRIMES простых чиселв стеке.Затем вытолкните каждый элемент из стека, чтобы распечатать его в обратном порядке.

Возможно, стоит также включить свою логику isPrime в ее собственную функцию, как только вы запустите ее.

0 голосов
/ 15 февраля 2011

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

  1. Если number простое число, поместите его в стек.
  2. Когда цикл первичного искателя заканчивается, начните выталкивать из стека в новом цикле. Числа будут отображаться в порядке убывания (потому что они были перенесены в порядке возрастания).
0 голосов
/ 15 февраля 2011

Во-первых, взгляните на Поиск простых чисел с помощью сита Эратосфена (Первоначально: есть ли лучший способ подготовить этот массив?) для обсуждения лучших способов поиска простых чисел. Затем используйте стек для изменения порядка на основе свойства «последний пришел, первый вышел».

0 голосов
/ 15 февраля 2011
  1. Прочитайте javadoc для стека и его родительского класса: Vector
  2. При вычислении 50 первых простых членов вместо их отображения во время их поиска сохраните ихстек
  3. Как только вы закончили поиск простых чисел, в стеке будут все найденные простые числа.Самый маленький - это первый элемент стека, а самый большой - последний элемент стека.Запустите еще один цикл с конца стека до начала, чтобы отобразить простые числа в порядке убывания.

Примечание. Стек - это старый класс, который больше не должен использоваться.Вы должны предпочесть ArrayList.

...