Форум программистов, компьютерный форум CyberForum.ru

Генерация чисел Хэмминга - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 61, средняя оценка - 4.89
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
09.09.2009, 22:00     Генерация чисел Хэмминга #1
Задание 2.24. Генерация чисел Хэмминга
Числами Хэмминга называются натуральные числа, которые среди своих делителей имеют только степени чисел 2, 3 и 5. Первые 10 упорядоченных по возрастанию чисел Хэмминга образует последовательность 1, 2, 3, 4, 5, 6, 8, 9, 10 и 12. Первому числу этого ряда соответствуют нулевые степени всех сомножителей. Составить программу, которая генерирует первые 1000 чисел Хэмминга.
Совет 1 (общий)
Конечно, можно построить цикл по перебору всех длинных целых чисел (а их — порядка двух миллиардов), в теле которого выделяются все делители, кратные 2, 3 и 5. Если результат деления тестируемого числа оказывается равным 1, т. е. у числа никаких других делителей нет, то найдено очередное число Хэмминга. Однако такая программа будет очень долго работать (для сравнения мы приведем и текой вариант решения).
Гораздо более эффективный алгоритм базируется на определении следующего числа Хэмминга по уже построенной последовательности. При этом приходится запоминать, какое из ранее найденных чисел необходимо домножить на 2, какое — на 3 и какое — на 5. Из трех возможных вариантов следует выбирать минимальное произведение. На первом шаге мы знаем единственное число Хэмминга, равное 1, и именно оно может быть умножено на следующем шаге на один из трех возмож-
ных множителей. Минимальное произведение равно 2, и это — второе число Хэмминга. Теперь умножению на 2 должно быть подвергнуто второе число, а умножению на 3 и 5 — пока еще первое. Поэтому на втором шаге минимальное произведение равно 3. После этого умножению на 2 и 3 может быть подвергнуто второе число, а на 5 — пока еще только первое. Одним словом, когда определено минимальное произведение, использованный множитель должен "переместиться" на следующее, уже найденное число Хэмминга.
Совет 2 (общий)
Обозначим через kl, k2, k3 индексы чисел Хэмминга, которые будут множиться соответственно на 2, 3 и 5. Их начальные значения в программе на Бейсике можно не задавать, т. к. все числовые переменные перед началом работы программы сбрасываются в ноль.
Программа 2_24.с (оптимальный вариант)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <conio.h>
main() (
long Xam[1000], н2, хЗ, к5;
int j;
int k2=0,k3=0,k5=0;
clrscr(); -
Xam[0]-l,-
printf("%4d %9d",l,l);
for(i=i; j<1000; j++) {
x2=Xam[k2]*2; x3=Xam[k3]*3; 
x5=Xam[k5]*5;
if(x2<=x3 && x2<=x5)
{Xam[j]=x2; k2++;}
if(x3<=x2 && x3<=x5)
{Xam[j]=x3; k3++;} 
if(x5<=x2 && x5<=x3)
{Xam[j]=x5; k5++;}
printf("\n%4d %91d",j,Xam[j]);
if(j % 20==0)
getch(); }
getch (); }

Дано такое задание, исправление ошибок в программе результата не дает((( В нете информацию про генерацию чисел хемминга найти не удалось Помогите пожалуйста, как сделать это задание?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.09.2009, 22:00     Генерация чисел Хэмминга
Посмотрите здесь:

Генерация чисел C++
Генерация чисел C++
C++ генерация случайных чисел
генерация чисел C++
C++ Генерация псевдослучайных чисел!!!
Генерация чисел C++
Генерация случайных чисел С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
^Tecktonik_KiLLeR
 Аватар для ^Tecktonik_KiLLeR
1144 / 426 / 19
Регистрация: 23.06.2009
Сообщений: 6,147
Завершенные тесты: 1
09.09.2009, 22:23     Генерация чисел Хэмминга #2
Цитата Сообщение от Sweet Dream Посмотреть сообщение
if(x2<=x3 && x2<=x5)
{Xam[j]=x2; k2++;}
if(x3<=x2 && x3<=x5)
{Xam[j]=x3; k3++;}
if(x5<=x2 && x5<=x3)
{Xam[j]=x5; k5++;}

C++
1
2
3
if(a=5){...}
if(a=6){...}
if(a=7){...}
Глава "Как не надо программировать программы"
То что тут делается,это последовательность операторов.
книга андрей богатырев
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
09.09.2009, 22:47  [ТС]     Генерация чисел Хэмминга #3
Самое интересное что мне нужно именно эту программу исправить(((
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9383 / 5433 / 916
Регистрация: 25.07.2009
Сообщений: 10,428
09.09.2009, 23:31     Генерация чисел Хэмминга #4
Цитата Сообщение от Sweet Dream Посмотреть сообщение
Самое интересное что мне нужно именно эту программу исправить(((
Проще заново написать. Это бред какой-то. Случайно не скан файнридером оцифрованный?
1.
Цитата Сообщение от Sweet Dream Посмотреть сообщение
long Xam[1000], н2, хЗ, к5;
int j;
int k2=0,k3=0,k5=0;
Так к5 - long или int? н2 больше вообще нигде не встречается, за то есть х2. Мало того, ещё и х5 присутствует. То есть видимо
C++
1
long Xam[1000], x2, хЗ, x5;
подразумевалось?
2.
Цитата Сообщение от Sweet Dream Посмотреть сообщение
clrscr(); -
Xam[0]-l,-
printf("%4d %9d",l,l);
в первой строчке минус лишний, а вторая больше клинопись напоминает. l нигде не определена, видимо вместо i появилась. И само "выражение" неверное. В третьей строке два раза выводится та самая нигде ранее не определённая l. В первый раз в поле шириной в 4 символа, второй - в 9...
3.
Цитата Сообщение от Sweet Dream Посмотреть сообщение
for(i=i; j<1000; j++){
видимо должно быть
C++
1
for(j=i; j<1000; j++){
?
Дальше вникать не стал. А в чём проблема-то, почему именно это выправлять надо, а не новую правильную програмку сделать?
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
09.09.2009, 23:42  [ТС]     Генерация чисел Хэмминга #5
Причуды преподавателя(( Сказано исправить вот эту прогу.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
10.09.2009, 02:15     Генерация чисел Хэмминга #6
Вот исправленная Ваша программа:
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
#include <conio.h>
#include <stdio.h>
 
int main() 
{
long Xam[1000], x2, x3, x5;
int j;
int k2=0,k3=0,k5=0;
clrscr(); 
Xam[0]=1;
printf("%4d %9d",0,1);
for(j=1; j<1000; j++) 
{
x2=Xam[k2]*2; x3=Xam[k3]*3; 
x5=Xam[k5]*5;
    if(x2<=x3 && x2<=x5)
    {
    Xam[j]=x2; k2++;
    }
    if(x3<=x2 && x3<=x5)
    {
    Xam[j]=x3; k3++;
    }
    if(x5<=x2 && x5<=x3)
    {
    Xam[j]=x5; k5++;
    }
printf("\n%4d %9d",j,Xam[j]);
if(j % 20==0)
getch(); 
}
getch (); 
return 0;
}
Есть один нюанс. У меня компилятор упорно (даже с подключением необходимых библиотечных файлов) не воспринимает функцию clrscr(). Если у Вас тоже будет выдавать на ней ошибку, или уберите эту строчку, или закоментируйте. Программа отлично работает и без этой строки.
inter
9696 / 2449 / 44
Регистрация: 06.03.2009
Сообщений: 8,503
10.09.2009, 02:20     Генерация чисел Хэмминга #7
Цитата Сообщение от Sweet Dream Посмотреть сообщение
Причуды преподавателя(( Сказано исправить вот эту прогу.
хороший препод,
"мозг должен работать" - не говорил он такой фразы? а то знакомый стиль
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
10.09.2009, 03:57  [ТС]     Генерация чисел Хэмминга #8
спасибо большое за помощь!!)) Вот только остался последний вопрос В оформлении отчета по работе сказано что "программа должна быть в виде функции" поэтому в отчете нужно выписать объявление функции, описание что она делает и возвращаемое значение С возвращаемым значением вроде как разобралась, а вот с объявлением функции проблема(((
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
10.09.2009, 10:08     Генерация чисел Хэмминга #9
valeriikozlov, clrscr() - это борландовская функция которая очищает экран. Аналог в MSVS и Dev-C++ -
C++
1
system("cls");
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
10.09.2009, 19:47  [ТС]     Генерация чисел Хэмминга #10
помогите пожалуйста, как разделить программу на main и отдельно функцию которая выполняет все вычисления? Помимо этого надо сделать так чтобы перед началом работы програмки можно было указать сколько чисел генерировать
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
11.09.2009, 10:36     Генерация чисел Хэмминга #11
Sweet Dream,
вот
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
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
void Xam(long *xam, int razm)
{   
    long x2, x3, x5;
    int j;
    int k2=0,k3=0,k5=0;
    xam[0]=1;
    printf("%4d %9d",0,1);
    for(j=1; j<razm; j++) 
    {
        x2=xam[k2]*2;
        x3=xam[k3]*3; 
        x5=xam[k5]*5;
        if(x2<=x3 && x2<=x5)
            xam[j]=x2; k2++;
        if(x3<=x2 && x3<=x5)
            xam[j]=x3; k3++;
        if(x5<=x2 && x5<=x3)
            xam[j]=x5; k5++;
    }
}
 
void Print(long *xam, int razm)
{
    int j;
    for(j=1; j<razm; j++) 
    {
        printf("\n%4d %9d",j,xam[j]);
        if(j % 20==0)
            getch(); 
    }
}
 
int main() 
{
    int kol;
    printf("Vvedite kolichestvo\n> ");
    scanf("%d", &kol);
    long *xam = (long *)malloc(kol* sizeof(long));
    Xam(xam, kol);
    Print(xam, kol);
    getch (); 
    return 0;
}
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
12.09.2009, 00:40  [ТС]     Генерация чисел Хэмминга #12
спасибо огромное за помощь))
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,315
12.09.2009, 11:16     Генерация чисел Хэмминга #13
10-th number is: 12
100-th number is: 1536
1000-th number is: 51200000
10000-th number is: 288325195312500000
100000-th number is: 290142196707511001929482240000000000000
1000000-th number is: 519312780448388736089589843750000000000000000000000000000000000000000000000000000000
10000000-th number is: 16244105063830431823239215311759575035108538820596640863335672483325211601368209812790155410766601562500000000000000000000000000000000000000000000000000000000000000000000000000000000
100000000-th number is: 18140143309611363532953342430693354584669635033709097929462505366714035156593135818380467866054222964635144914854949550271375442721368122191972041094311075107507067573147191502194201568268202614781694681859513649083616294200541611489469967999559505365172812095568020073934100699850397033005903158113691518456912149989919601385875227049401605594538145621585911726469930727034807205200195312500

10-th
100
1000
10000
100000
1000000 0.1 минуты
10000000 2.2 минуты
100000000 46 минут
1000000000 погноз 15-20 часов
10000000000 прогноз 15-25 суток
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
15.09.2009, 20:10  [ТС]     Генерация чисел Хэмминга #14
Цитата Сообщение от M128K145 Посмотреть сообщение
Sweet Dream,
вот
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
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
void Xam(long *xam, int razm)
{   
    long x2, x3, x5;
    int j;
    int k2=0,k3=0,k5=0;
    xam[0]=1;
    printf("%4d %9d",0,1);
    for(j=1; j<razm; j++) 
    {
        x2=xam[k2]*2;
        x3=xam[k3]*3; 
        x5=xam[k5]*5;
        if(x2<=x3 && x2<=x5)
            xam[j]=x2; k2++;
        if(x3<=x2 && x3<=x5)
            xam[j]=x3; k3++;
        if(x5<=x2 && x5<=x3)
            xam[j]=x5; k5++;
    }
}
 
void Print(long *xam, int razm)
{
    int j;
    for(j=1; j<razm; j++) 
    {
        printf("\n%4d %9d",j,xam[j]);
        if(j % 20==0)
            getch(); 
    }
}
 
int main() 
{
    int kol;
    printf("Vvedite kolichestvo\n> ");
    scanf("%d", &kol);
    long *xam = (long *)malloc(kol* sizeof(long));
    Xam(xam, kol);
    Print(xam, kol);
    getch (); 
    return 0;
}
хм, странно((( но результат программа выдает неправильный Она просто умножает каждое предыдущее число на 2, а 15-е число вовсе отрицательное
Получается
0 1
1 2
2 4
3 8
...
14 16384
15 -32768
а после 15-го числа вообще одни нули(( Помогите разобраться в чем ошибка
И еще такой вопрос в программе как я поняла функция void Xam генерирует эту самую последовательность,так? А что делает функция Print? выводит на печать результат?
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
15.09.2009, 20:46     Генерация чисел Хэмминга #15
Sweet Dream, да, извини, это банальная невнимательность В 17, 19 и 21 надо поставить вместо первых точки с запятой просто запятую.
вот так
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
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
void Xam(long *xam, int razm)
{       
    long x2, x3, x5;
    int j;
    int k2=0,k3=0,k5=0;
    xam[0]=1;
    printf("%4d %9d",0,1);
    for(j=1; j<razm; j++) 
    {
        x2=xam[k2]*2;
        x3=xam[k3]*3; 
        x5=xam[k5]*5;
        if(x2<=x3 && x2<=x5)
            xam[j]=x2, k2++;
        if(x3<=x2 && x3<=x5)
            xam[j]=x3, k3++;
        if(x5<=x2 && x5<=x3)
            xam[j]=x5, k5++;
    }
}
 
void Print(long *xam, int razm)
{
    int j;
    for(j=1; j<razm; j++) 
    {
        printf("\n%4d %9d",j,xam[j]);
        if(j % 20==0)
            getch(); 
    }
}
 
int main() 
{
    int kol;
    printf("Vvedite kolichestvo\n> ");
    scanf("%d", &kol);
    long *xam = (long *)malloc(kol* sizeof(long));
    Xam(xam, kol);
    Print(xam, kol);
    getch (); 
    return 0;
}
Да, Xam - генератор, а Print - выводит на печать
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
15.09.2009, 20:55  [ТС]     Генерация чисел Хэмминга #16
M128K145, спасибо!!))
и еще вопрос не могу понять переменные razm и kol
kol-это переменная количества выводимых чисел, а что тогда razm? и как они связаны между собой?
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
15.09.2009, 20:59     Генерация чисел Хэмминга #17
kol - да, это количество элементов.
razm - это параметр функции Xam, на место которого при вызове этой функции подставится kol. Собственно это видно в 42 строке
C++
1
Xam(xam, kol);
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
15.09.2009, 21:09  [ТС]     Генерация чисел Хэмминга #18
M128K145, понятно, значит та же самая подстановка происходит и в 43 строке при вызове функции Print
А что делается в 41-й строке?
C++
1
long *xam = (long *)malloc(kol* sizeof(long));
В википедии нашла информацию о malloc и calloc http://ru.wikipedia.org/wiki/Malloc но не очень поняла изложенный там материал( Если можно, чуть попроще "на пальцах" что это и для чего используется в этой программе?
M128K145
Эксперт C++
 Аватар для M128K145
8276 / 3495 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
15.09.2009, 21:14     Генерация чисел Хэмминга #19
long *xam = (long *)malloc(kol* sizeof(long));
long *xam - указатель на массив типа long
(long *)malloc - явное приведению к типу long* (указатель на переменную типа long)
malloc(kol* sizeof(long)) - динамическое выделение памяти под kol* sizeof(long) байт, где
kol - количество элементов в массиве умноженое на размер типа long (это значение как раз и возвращает sizeof())

В общем в ОЗУ выделяется последовательный блок памяти в kol* sizeof(long) байт под наш массив
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2009, 21:18     Генерация чисел Хэмминга
Еще ссылки по теме:

C++ генерация чисел
генерация случайных чисел C++
C++ Генерация чисел
C++ Генерация псевдослучайных чисел.с++
Генерация псевдослучайных чисел C++

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

Или воспользуйтесь поиском по форуму:
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
15.09.2009, 21:18  [ТС]     Генерация чисел Хэмминга #20
M128K145, спасибо большое за помощь)))
Если завтра сдам работу обязательно отпишусь здесь)) А если нет, то тоже отпишусь но уже наверно с новыми вопросами.))
Yandex
Объявления
15.09.2009, 21:18     Генерация чисел Хэмминга
Ответ Создать тему
Опции темы

Текущее время: 18:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru