Форум программистов, компьютерный форум, киберфорум
PascalABC.NET
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.54/13: Рейтинг темы: голосов - 13, средняя оценка - 4.54
0 / 0 / 0
Регистрация: 03.03.2019
Сообщений: 12

Последовательность Хемминга образуют натуральные числа не имеющие других простых делителей, кроме 2,3,5. найти первые n

27.01.2020, 09:58. Показов 2760. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Последовательность Хемминга образуют натуральные числа не имеющие других простых делителей, кроме 2,3,5. найти первые n чисел данной последовательности.
Если не сложно, то программу по легче)
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
27.01.2020, 09:58
Ответы с готовыми решениями:

Найти первые N элементов последовательности Хэмминга - числа, не имеющие других делителей кроме 2, 3, 5
Вывести на экран и сохранить в файл результат первые N элементов последовательности Хэмминга - числа, не имеющие других делителей...

Даны натуральные числа N и M. Найти такие натуральные числа, не имеющие общих делителей
Добрый день. Может кто может помочь. За ранее благодарен. Создать проект следующего вида: Условие: Даны натуральные числа N и M....

Даны натуральные числа m и n. Найти такие натуральные p и q, не имеющие общих делителей, что p/q = m/n
Даны натуральные числа m и n. Найти такие натуральные p и q, не имеющие общих делителей, что p/q = m/n.

14
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
27.01.2020, 12:01
Ограничение на N какое?
0
0 / 0 / 0
Регистрация: 03.03.2019
Сообщений: 12
27.01.2020, 14:38  [ТС]
В пределах integer
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
27.01.2020, 16:55
при n = 10000, число равное 8649755859375000000. Какой integer?
0
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
27.01.2020, 18:52
Цитата Сообщение от eaa Посмотреть сообщение
Какой integer?
Значит будет BigInteger, почему нет?

Можно бы mod-ами, но для n = 10000 это больно.
Если с этой стороны посмотреть задача интересная, так что вот:
Pascal
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
type
  // содержит или данные, или 2 ветки
  SortedTree<T> = sealed class where T: IComparable<T>;
    l,r: SortedTree<T>; // l <= r
    data: T;
    l_min,l_max, r_min,r_max: T;
    
    constructor(data: T);
    begin
      self.data := data;
      self.l_min := data;
      self.r_max := data;
    end;
    
    procedure UpdateL(node: SortedTree<T>);
    begin
      self.l := node;
      if node=nil then exit;
      self.l_min := node.l_min;
      self.l_max := node.r_max;
    end;
    
    procedure UpdateR(node: SortedTree<T>);
    begin
      self.r := node;
      if node=nil then exit;
      self.r_min := node.l_min;
      self.r_max := node.r_max;
    end;
    
    constructor(l,r: SortedTree<T>);
    begin
      UpdateL(l);
      UpdateR(r);
    end;
    
//    function IsDataNode := (l=nil) and (r=nil);
    function IsDataNode := r=nil; // для данной задачи должно быть достаточно
    /// Deq на ноде, у которой IsDataNode=true - не ожидается
    function Deq: T;
    begin
      if l.IsDataNode then
      begin
        Result := l.data;
        self.data := r.data;
        self.UpdateL( r.l );
        self.UpdateR( r.r );
      end else
        Result := l.Deq;
    end;
    
    function Minimize: SortedTree<T>;
    begin
      Result := (l<>nil) or (r=nil) ? self : r;
      Result.l := Result.l?.Minimize;
      Result.r := Result.r?.Minimize;
    end;
    
    function Enq(el: T): SortedTree<T>;
    begin
      if not self.IsDataNode then
      begin
        Result := self;
        // предпочтение левой ветке, чтоб немного уменьшить скорость создания новых нод
        //(удаление всегда начинается слева, поэтому Minimize постоянно убивает текущую ноду, а enq сразу создаёт новые в правой, поэтому неравномерно)
        if el.CompareTo(self.r_min)<0 then
          Result.UpdateL( l.Enq(el) ) else
          Result.UpdateR( r.Enq(el) );
      end else
      begin
        var comp := self.data.CompareTo(el);
        Result :=
        comp=0 ?
          self : // потому что 2*3 и 3*2
        comp<0 ?
          new SortedTree<T>(
            self, new SortedTree<T>(el)
          ) :
          new SortedTree<T>(
            new SortedTree<T>(el), self
          );
      end;
    end;
    
    procedure Println(tabs: integer := 0);
    begin
      if IsDataNode then
        Writeln($'{#9*tabs}Node[{self.data}]') else
      begin
        Writeln($'{#9*tabs}Range[{l_min}..{r_max}]');
        l.Println(tabs+1);
        r.Println(tabs+1);
      end;
    end;
    
  end;
  
function hem: sequence of BigInteger;
begin
  yield 1; // не гуглил, это тут надо?
  
  // работает и с <integer>, но тогда n очень ограничено
  var prev := new SortedTree<BigInteger>(2);
  prev := prev.enq(3);
  prev := prev.enq(5);
  
  while true do
  begin
    // дебаг. а ещё красиво
//    prev.Println;
//    Writeln('='*50);
//    Readln;
    
    var val := prev.Deq;
    prev := prev.Minimize;
    yield val;
    
    prev := prev.Enq(val*2);
    prev := prev.Enq(val*3);
    prev := prev.Enq(val*5);
    
  end;
  
end;
 
begin
  hem.Skip(10000).Take(30)
//  .ForEach(el->begin end);
  .PrintLines;
end.
Всего пару секунд, и вот уже числа с номерами от 10001 до 10030, потому что сложность O(n):
Code
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
288555831593533440
288881654523494400
289207845356544000
289910292480000000
290237644800000000
290565366750000000
291600000000000000
291929260253906250
292162779488452608
292492675205038080
292822943423500800
292968750000000000
293534171136000000
293865615360000000
294197433834375000
294912000000000000
295245000000000000
296148833645101056
296483230216294560
296630859375000000
296868139499520000
297203348275200000
297538935552000000
298023223876953125
298598400000000000
298935562500000000
300000000000000000
300189270593998242
300338745117187500
300578991243264000
Только, кхм, конечно тоже большие, но с eaa, не сходится.
0
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
27.01.2020, 19:01
Sun Serega, лучше передавать компаратор в виде объекта, поскольку тип T может по умолчанию не поддерживать сравнение. Более того, хорошо бы:
- ставить явно модификаторы доступа; инкапсуляция у Вас нарушена
- реализовать стандартные интерфейсы коллекций; плохая совместимость со стандартными структурами данных
- вынести Println из класса и сделать методом расширения; я не видел коллекций, где бы подобный метод был стандартным
, но это лишь в том случае, если хочется сделать качественную структуру данных.

Как говорится, пишите код так, будто его проверять будет бешенный психопат.
0
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
27.01.2020, 19:04
Модификаторы доступа в принципе можно, но поля должны отображаться приватными только для hem (и работать это будет всё равно только визуально). В отличии от огромного модуля OpenCLABC (он был предыдущей целью предирок) - тут оно того не стоит.

Ну и, это основываясь на том, что я не рассчитывал использование этого модуля вне этой задачи. Если ещё где то понадобиться - я скорее с 0 напишу.

По той же причине нет смысла в кастомных компараторах (хотя про них я изначально не подумал), только усложняет код. Кроме integer, int64 и BigInteger в качестве шаблонного параметра ничего не ожидалось изначально.

А Println - посмотрите внимательно, это не как метод последовательности. Это только красивый дебаговый вывод дерева. Именно дерева, не последовательности в нём. Я это использовал чтоб проверять значение полей вроде l_min.
0
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
27.01.2020, 19:06
Цитата Сообщение от Sun Serega Посмотреть сообщение
А Println - посмотрите внимательно, это не как метод последовательности. Это только красивый дебаговый вывод дерева. Именно дерева, не последовательности в нём. Я это использовал чтоб проверять значение полей вроде l_min.
Можно было бы переопределить метод ToString для красивого вывода.

Цитата Сообщение от Sun Serega Посмотреть сообщение
(он был предыдущей целью предирок)
Которые кто-то не захотел исправлять, ибо мелочи, а также поддержал своего помощника, который открыто матерился в репозитории (скриншот имеется). Но, всё большое состоит из мелочей, если игнорировать мелочи, то что будет в итоге? Если не хотите, чтобы он попал сюда, то лучше Вам не упоминать про свой репозиторий сейчас.
0
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
27.01.2020, 19:13
Цитата Сообщение от Соколиный глаз Посмотреть сообщение
Можно было бы переопределить метод ToString для красивого вывода.
Можно, но тогда пришлось бы париться с StringBuilder. Хотя это конечно быстрее чем
Цитата Сообщение от Sun Serega Посмотреть сообщение
$'{#9*tabs}
Но опять же, какая разница по скорости для метода дебага.

Единственное что действительно стоило сделать - так это:
Pascal
1
2
3
4
5
6
7
8
    procedure Println(tabs: integer := 0) :=
    if IsDataNode then
      Writeln($'{#9*tabs}Node[{self.data}]') else
    begin
      Writeln($'{#9*tabs}Range[{l_min}..{r_max}]');
      l.Println(tabs+1);
      r.Println(tabs+1);
    end;
Потому что простота в данном случае важнее.

Добавлено через 3 минуты
Лучше скажите что по результату, а не красоте кода. Результаты то не сходятся с тем что сказал eaa. Хотя я сам не проверял. То что я нашёл (не сильно поискав) - это очень интересная но сложная статья про то как этот хеминг боролся с ошибками памяти доисторических компов.
0
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
27.01.2020, 19:14
Цитата Сообщение от Sun Serega Посмотреть сообщение
это очень интересная но сложная статья про то как этот хеминг боролся с ошибками памяти доисторических компов
Не поделитесь?
0
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
27.01.2020, 19:21
Первая же страница википедии в гугле
https://ru.wikipedia.org/wiki/Код_Хэмминга
0
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
27.01.2020, 22:09
Цитата Сообщение от Sun Serega Посмотреть сообщение
Только, кхм, конечно тоже большие, но с eaa, не сходится.
Думал 2,3, 5 обязательно должно входить.
если не так то ответ для n = 10000 будет 288325195312500000

это ужас какой то, 40 тыс элементов считает 8 секунд.


написал 10 строчек кода, 3 миллиона элементов считает 8+ секунд.
0
 Аватар для Sun Serega
2355 / 1458 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
27.01.2020, 23:11
Цитата Сообщение от eaa Посмотреть сообщение
написал 10 строчек кода, 3 миллиона элементов считает 8+ секунд.
Так а чего не прикладываете то?
0
0 / 0 / 0
Регистрация: 03.03.2019
Сообщений: 12
29.01.2020, 12:45  [ТС]
Можно код, где используются только ветвления и циклы?
На уровне 10 класса.
0
80 / 33 / 10
Регистрация: 14.06.2019
Сообщений: 516
29.01.2020, 13:09
Цитата Сообщение от Axifor Посмотреть сообщение
Можно код, где используются только ветвления и циклы?
На уровне 10 класса.
Ветвления и циклы - это код примерно 4-6 класса. Чем вас этот не устраивает?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
29.01.2020, 13:09
Помогаю со студенческими работами здесь

Найти такие натуральные числа P и Q, не имеющие общих делителей, что P/Q = M/N
1) Даны натуральные числа M и N. Найти такие натуральные числа P и Q, не имеющие общих делителей, что P/Q = M/N. 2) Даны натуральное...

Сократить дробь т.е. найти такие натуральные числа p и q не имеющие общих делителей
Даны натуральные числа a и b, обозначающие соответственно числитель и знаменатель дроби. Сократить дробь т.е. найти такие натуральные числа...

Циклы. Найти все натуральные числа, имеющие наибольшее количество делителей в заданной последовательности
В решённой программе Помогите доразбираться с задачей var c,d,x,s,maxd,i,y,a:integer; Begin maxd:=0; s:=0; Write('Введите...

Найти все натуральные четырехзначные числа, цифры в которых образуют возрастающую последовательность
решить литерными найти все натуральные четырехзначные числа,цифры в которых образуют возрастающую последовательность.

Найти все натуральные числа, цифры в которых образуют строго возрастающую последовательность
Найти все натуральные n-значные числа, цифры в которых образуют строго возрастающую последовательность (например, 1234, 5789).


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT
bedvit 28.01.2026
Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .
SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 28.01.2026
Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru