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

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

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

Новые блоги и статьи Все статьи Все блоги /
Модель по догадкам anaschu 25.08.2026 Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .	Запись в регистр сведений независимо от заполненности табличной части Maks 25.08.2026 Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .	Ноутбук Альфария kumehtar 24.08.2026 Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?	Мастера простых решений DevAlt 23.08.2026 В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
Цена ошибки DevAlt 23.08.2026 Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .	Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. zorxor 22.08.2026 Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .	Жизня: рисунок укладки багажа, сделанный клодом anaschu 21.08.2026 Сделал 15 снимков, он по снимкам сделал схему.	Был там один разговор по поводу свободы в материальном мире. kumehtar 19.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

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

Решение