Функция, реализованная на очереди, должна возвращать список делителей

@Hacavvo · Регистрация: 31.10.2021

Студворк — интернет-сервис помощи студентам

Задана некоторая последовательность натуральных чисел. Напечать в порядке увеличение N таких чисел последовательности, в разложение которых на простые множители входят только простые числа A, B, C в любой комбинации.
К примеру, если А = 2, В = 3, С = 5, то первые 10 чисел будут 2, 3, 4, 5, 6, 8,9, 10, 12, 15.
Функция должна возвращать List<int>, и всё это должно быть решено с помощью очереди.

Если я ввожу 2, 3, 5, всё действительно работает как надо, но при 3 5 7 должно выводить (3 5 7 9 15 21 25 35 49) а выводит совсем другое.

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
using System;
using System.Collections.Generic;
 
namespace ConsoleApp8
{
    class Program
    {
        interface ILab8QueuePartBasicLevel
        {
            public int A { get; set; }
            public int B { get; set; }
            public int C { get; set; }
            public List<int> GetSequence(int N);
        }
 
        public class Queue: ILab8QueuePartBasicLevel
        {
 
            public Queue(int a, int b, int c)
            {
                A = a;
                B = b;
                C = c;
            }
 
            public int A { get; set; }
 
            public int B { get; set; }
 
            public int C { get; set; }
 
            private Queue<int> isPrime(int num)
            {
                var queue = new Queue<int>();
                for (int i = 3; i <= num; i += 2)
                {
                    if (num % i == 0)
                    {
                        queue.Enqueue(i);
                        num /= i;
                   
                    }
                }
                return queue;
            }
 
            public List<int> GetSequence(int N)
            {
                List<int> numbers = new List<int>() { };
                var result = new Queue<int>();
                int i = A ;
                for (; ;)
                {
                    int temp = 0;
                    result = isPrime(i);
 
                    foreach (var elem in result)
                        if (elem != A && elem != B && elem != C) temp = 1;
                    if (temp == 0) numbers.Add(i);
                    if (numbers.Count == N)
                    {
                        break;
                    }
                    i++;
                }
                return numbers;
            }
        }
        static void Main()
        {
            string input;
            Console.WriteLine("Input number A: ");
            input = Console.ReadLine();
            int A = Convert.ToInt32(input);
            Console.WriteLine("Input number B: ");
            input = Console.ReadLine();
            int B = Convert.ToInt32(input);
            Console.WriteLine("Input number C: ");
            input = Console.ReadLine();
            int C = Convert.ToInt32(input);
            Console.WriteLine("How many numbers do you want to get?: ");
            input = Console.ReadLine();
            int result = Convert.ToInt32(input);
            Queue newqueue = new Queue(A, B, C);
            var arr = newqueue.GetSequence(result);
            for (int i = 0; i < arr.Count; i++)
            {
                Console.Write(arr[i] + " ");
            }
        }
    }
}

P.S: нашел решение подобной задачи на форуме, но на С++

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int n;
    cin >> n;
 
    priority_queue<int, vector<int>, greater<int> > pq;
    for (int i : { 2, 3, 5 }) pq.push(i);
 
    while (n--) {
        int v = pq.top();
        while (pq.top() == v) pq.pop();
        cout << v << ' ';
        for (int i : { v * 2, v * 3, v * 5 }) pq.push(i);
    }
 
    return 0;

memphis · 24.11.2021, 00:51

Сообщение от wizard41

Думаю, что очередь должна быть создана из тех чисел, простыми делителями которых и являются эти A,B,C

Так это как? Сначала в очередь, а потом в список? Типа, память не наша и мы её не щадим... ))

Сообщение от wizard41

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

Хотя... Возможно. Точно Химера получится. )))

@Элд Хасп · 24.11.2021, 00:51

Сообщение от wizard41

Для этого прочесываем очередь и заносим в список элементы

Где-то мне попадались алгоритмы создания сортированных очередей.
Возможно здесь имеется виду использование подобного.
Может быть в учебном курсе TC должен был проходить их до этого задания.

memphis · 24.11.2021, 00:56

Сообщение от Элд Хасп

Здесь нужно находить кратные, а не делители.

Мда. А я понял, что как раз мы исследуем каждое число из последовательности:

Сообщение от Hacavvo

Задана некоторая последовательность натуральных чисел

Добавлено через 2 минуты

Сообщение от wizard41

так делители и так заданы (A,B,C). Зачем их пихать в очередь?

Дык если бы я знал? Говорю же - Франкенштейн!

@wizard41 · 24.11.2021, 00:59

Сообщение от memphis

Сначала в очередь

без всякого начала. В очередь заносятся только элементы, подпадающие под условие, вплоть до N.

Добавлено через 1 минуту

Сообщение от memphis

Франкенштейн!

Завтра у него и спросим. Лично

memphis · 24.11.2021, 00:59

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

memphis · 24.11.2021, 01:00

Сообщение от wizard41

без всякого начала. В очередь заносятся только элементы, подпадающие под условие, вплоть до N.

А в список тогда что?

@wizard41 · 24.11.2021, 01:02

Сообщение от memphis

А в список тогда что?

Отсортированные значения.

memphis · 24.11.2021, 01:02

Сообщение от memphis

А в список тогда что?

А, ну да. Сортируем на очереди и потом в список. Блин, но сортировка на очереди - это...

@Hacavvo · 24.11.2021, 01:02 **[ТС]**

memphis, чувствую себя абсолютно также, код который вы приводил выше вроде бы работает и проходит все проверки. Но опять же, не понимаю зачем тогда очереди в условии (при том несколько) нужны.

@wizard41 · 24.11.2021, 01:03

Сообщение от memphis

А в список тогда что?

Это такой же вопрос, как "А зачем тут очередь вообще?"

memphis · 24.11.2021, 01:12

Ща надо болванку класса слепить. Как назовём-то?

@Hacavvo · 24.11.2021, 01:13 **[ТС]**

memphis, NameExample

@Элд Хасп · 24.11.2021, 01:13

Hacavvo, если нигде не косячил, то вот на очередях:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
using System;
using System.Collections.Generic;
 
/// <summary>Типы и методы различных данных.</summary>
namespace Data
{
    public interface IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
        public List<int> GetSequence(int N);
    }
 
    public class ListOfMultiples : IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
 
        /// <summary>Добавление в очередь с сохранением сортировки.</summary>
        /// <param name="queue">Сортировання очередь.</param>
        /// <param name="number">Добавляемы элемент.</param>
        /// <remarks>Вся очередь считывается по кругу и элемент добавляется перед первым большим его.</remarks>
        public static void SortDequeue(Queue<int> queue, int number)
        {
            bool isAdded = false;
            for (int i = 0; i < queue.Count; i++)
            {
                int current = queue.Dequeue();
                if (!isAdded && current > number)
                {
                    queue.Enqueue(number);
                    isAdded = true;
                }
                queue.Enqueue(current);
            }
            if (!isAdded)
            {
                queue.Enqueue(number);
            }
 
        }
 
        public static void SortDequeue(Queue<int> queue, params int[] numbers)
        {
            foreach (var number in numbers)
            {
                SortDequeue(queue, number);
            }
        }
 
        public List<int> GetSequence(int N)
        {
            if (A <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(A));
            if (B <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(B));
            if (C <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(C));
 
            List<int> list = new List<int>();
            Queue<int> factors = new();
            SortDequeue(factors, A, B, C);
            Queue<int> multiples = new();
            SortDequeue(multiples, A, B, C);
 
            while (list.Count < N)
            {
                int current = multiples.Dequeue();
                list.Add(current);
                if (list.Count >= N)
                    break;
 
                for (int i = 0; i < factors.Count; i++)
                {
                    int factor = factors.Dequeue();
                    int mult = current * factor;
 
                    SortDequeue(multiples, mult);
                    factors.Enqueue(factor);
                }
            }
 
            return list;
        }
    }
}

@wizard41 · 24.11.2021, 01:14

Сообщение от memphis

но сортировка на очеред

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

Добавлено через 1 минуту

Сообщение от memphis

Как назовём-то?

CrazyQueueMTF()

memphis · 24.11.2021, 01:18

Элд Хасп, очень надеюсь, что автору подойдёт. Ибо впрягаться писать эту муть желание напрочь пропало. Я тут и в рассуждениях постоянно блужу, как трёх соснах. А как писать начну, так и потеряюсь, что именно я сейчас делаю )))

Добавлено через 34 секунды

Сообщение от wizard41

CrazyQueueMTF()

Точно Crazy ))

@Hacavvo · 24.11.2021, 01:21 **[ТС]**

Элд Хасп, попробовал ваш код, выводит 3, 5, 9,15, 7, 35, 15 и т.д, то-есть не так как то

memphis · 24.11.2021, 01:21

Сообщение от wizard41

CrazyQueueMTF()

Да, насчёт Crazy - в точку. (Что-то один ответ пропал. Наверное завтра появится)

@Элд Хасп · 24.11.2021, 01:42

Сообщение от Hacavvo

попробовал ваш код, выводит 3, 5, 9,15, 7, 35, 15 и т.д, то-есть не так как то

Да, не учёл что размер очереди меняется при добавление элемента и что одно и тоже число может быть получено разным сочетанием делителей (2*3=3*2).
Вот исправленный вариант:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
using System;
using System.Collections.Generic;
 
/// <summary>Типы и методы различных данных.</summary>
namespace Data
{
    public interface IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
        public List<int> GetSequence(int N);
    }
 
    public class ListOfMultiples : IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
 
        /// <summary>Добавление в очередь с сохранением сортировки.</summary>
        /// <param name="queue">Сортировання очередь.</param>
        /// <param name="number">Добавляемы элемент.</param>
        /// <remarks>Вся очередь считывается по кругу и элемент добавляется перед первым большим его.</remarks>
        public static void SortDequeue(Queue<int> queue, int number)
        {
            bool isAdded = false;
            int count = queue.Count;
            for (int i = 0; i < count; i++)
            {
                int current = queue.Dequeue();
                if (!isAdded && current > number)
                {
                    queue.Enqueue(number);
                    isAdded = true;
                }
                queue.Enqueue(current);
            }
            if (!isAdded)
            {
                queue.Enqueue(number);
            }
 
        }
 
        public static void SortDequeue(Queue<int> queue, params int[] numbers)
        {
            foreach (var number in numbers)
            {
                SortDequeue(queue, number);
            }
        }
 
        public List<int> GetSequence(int N)
        {
            if (A <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(A));
            if (B <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(B));
            if (C <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(C));
 
            List<int> list = new List<int>();
            Queue<int> factors = new();
            SortDequeue(factors, A, B, C);
            Queue<int> multiples = new();
            SortDequeue(multiples, A, B, C);
 
            while (list.Count < N)
            {
                int current = multiples.Dequeue();
                if (list.BinarySearch(current) < 0)
                    list.Add(current);
                if (list.Count >= N)
                    break;
 
                for (int i = 0; i < factors.Count; i++)
                {
                    int factor = factors.Dequeue();
                    int mult = current * factor;
 
                    SortDequeue(multiples, mult);
                    factors.Enqueue(factor);
                }
            }
 
            return list;
        }
    }
}

Добавлено через 6 минут
Вот так лучше:

C#
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
        public List<int> GetSequence(int N)
        {
            if (A <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(A));
            if (B <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(B));
            if (C <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(C));
 
            List<int> list = new List<int>();
            Queue<int> factors = new();
            SortDequeue(factors, A, B, C);
            Queue<int> multiples = new();
            SortDequeue(multiples, A, B, C);
 
            while (list.Count < N)
            {
                int current = multiples.Dequeue();
                list.Add(current);
                if (list.Count >= N)
                    break;
 
                for (int i = 0; i < factors.Count; i++)
                {
                    int factor = factors.Dequeue();
                    int mult = current * factor;
 
                    if (!multiples.Contains(mult))
                        SortDequeue(multiples, mult);
                    factors.Enqueue(factor);
                }
            }
 
            return list;
        }

@Элд Хасп · 24.11.2021, 02:01

Hacavvo, без очередей, конечно, всё будет намного проще, короче, быстрее:

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using System;
using System.Collections.Generic;
 
/// <summary>Типы и методы различных данных.</summary>
namespace Data
{
    public interface IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
        public List<int> GetSequence(int N);
    }
 
    public class ListOfMultiples : IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
 
        public List<int> GetSequence(int N)
        {
            if (A <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(A));
            if (B <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(B));
            if (C <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(C));
 
            List<int> list = new List<int>();
            List<int> factors = new() { A, B, C };
            SortedSet<int> multiples = new(factors);
 
            while (list.Count < N)
            {
                int current = multiples.Min;
                multiples.Remove(current);
                list.Add(current);
                if (list.Count >= N)
                    break;
 
                for (int i = 0; i < factors.Count; i++)
                {
                    int factor = factors[i];
                    int mult = current * factor;
 
                    multiples.Add(mult);
                }
            }
 
            return list;
        }
    }
}

@ArtemGubarev · 24.11.2022, 20:57

Элд Хасп,

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
    public class ListOfMultiples : IListOfMultiples
    {
        public int A { get; set; }
        public int B { get; set; }
        public int C { get; set; }
 
        public List<int> GetSequence(int N)
        {
            if (A <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(A));
            if (B <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(B));
            if (C <= 0)
                throw new ArgumentException("Должен быть положительным.", nameof(C));
 
            List<int> list = new List<int>();//cписок для вводимых чисел
            List<int> factors = new() { A, B, C };//список кратных
            SortedSet<int> multiples = new(factors);//?
 
            while (list.Count < N)
            {
                int current = multiples.Min;//не понимаю для чего "multiples"
                multiples.Remove(current);
                list.Add(current);
                if (list.Count >= N)
                    break;
 
                for (int i = 0; i < factors.Count; i++)
                {
                    int factor = factors[i];
                    int mult = current * factor;
 
                    multiples.Add(mult);
                }
            }
 
            return list;
        }
    }
}

Не подскажите что делают отмеченные строки. И такой вопрос, как взаимодействовать с этим классом

Новые блоги и статьи Все статьи Все блоги /
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .	[EasyBuilder Pro] Памятка по разработке для панелей Weintek ФедосеевПавел 26.08.2026 Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .	Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .

memphis 740 / 284 / 83 Регистрация: 12.12.2012 Сообщений: 564
	24.11.2021, 00:59
	Hacavvo, а где вы учитесь? Если не секрет, конечно. Просто глядя на это задание и не понимая его, я чувствую себя очень ущербным. Прям, вот баран и не больше того. ))) 0

@Hacavvo 0 / 0 / 0 Регистрация: 31.10.2021 Сообщений: 16
	24.11.2021, 01:02 [ТС]
	memphis, чувствую себя абсолютно также, код который вы приводил выше вроде бы работает и проходит все проверки. Но опять же, не понимаю зачем тогда очереди в условии (при том несколько) нужны. 0

memphis 740 / 284 / 83 Регистрация: 12.12.2012 Сообщений: 564
	24.11.2021, 01:12
	Ща надо болванку класса слепить. Как назовём-то? 0

@Hacavvo 0 / 0 / 0 Регистрация: 31.10.2021 Сообщений: 16
	24.11.2021, 01:13 [ТС]
	memphis, NameExample 0

@Hacavvo 0 / 0 / 0 Регистрация: 31.10.2021 Сообщений: 16
	24.11.2021, 01:21 [ТС]
	Элд Хасп, попробовал ваш код, выводит 3, 5, 9,15, 7, 35, 15 и т.д, то-есть не так как то 0

Функция, реализованная на очереди, должна возвращать список делителей

Решение