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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 61, средняя оценка - 4.89
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
#1

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

09.09.2009, 22:00. Просмотров 8674. Ответов 19
Метки нет (Все метки)

Задание 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 (); }

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

Генерация чисел - C++
Доброго времени суток, не могли бы вы подсказать как выбрать рандомно число из двух чисел 2 и 4 и в диапозоне от 1 до 4 благодарю

Генерация чисел - C++
Помогите написать программу, а мучусь уже два часа. :) Нужно сгенерировать 30 трёхзначных чисел, и что бы в цифры этих чисел не были...

Генерация чисел - C++
Нужно программа для генерации тризначных чисел и таких, что бы в этих числах них не было парных цифр. ТИпу, если число &quot;ХХХ&quot;, то &quot;Х&quot; не...

генерация чисел - C++
Скажите, пожалуйста, как сгенерировать случайным образом отрицательные числа?

Генерация чисел - C++
Вообщем мне нужно сгенерировать отрицательное вещественное число с 2 цифрами целой и 2 цифрами дробной части. Отрицательное ведь так...

генерация чисел - C++
написать прогу, которая генерирует последовательность из 10 случайных чисел в диапозоне от 1 до 10, выводит эти числа на экран и вычисляет...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
^Tecktonik_KiLLeR
1160 / 442 / 22
Регистрация: 23.06.2009
Сообщений: 6,245
Завершенные тесты: 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){...}
Глава "Как не надо программировать программы"
То что тут делается,это последовательность операторов.
книга андрей богатырев
0
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
09.09.2009, 22:47  [ТС] #3
Самое интересное что мне нужно именно эту программу исправить(((
0
easybudda
Модератор
Эксперт CЭксперт С++
9633 / 5581 / 948
Регистрация: 25.07.2009
Сообщений: 10,715
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++){
?
Дальше вникать не стал. А в чём проблема-то, почему именно это выправлять надо, а не новую правильную програмку сделать?
1
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
09.09.2009, 23:42  [ТС] #5
Причуды преподавателя(( Сказано исправить вот эту прогу.
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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(). Если у Вас тоже будет выдавать на ней ошибку, или уберите эту строчку, или закоментируйте. Программа отлично работает и без этой строки.
2
inter
9702 / 2457 / 47
Регистрация: 06.03.2009
Сообщений: 8,503
10.09.2009, 02:20 #7
Цитата Сообщение от Sweet Dream Посмотреть сообщение
Причуды преподавателя(( Сказано исправить вот эту прогу.
хороший препод,
"мозг должен работать" - не говорил он такой фразы? а то знакомый стиль
1
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
10.09.2009, 03:57  [ТС] #8
спасибо большое за помощь!!)) Вот только остался последний вопрос В оформлении отчета по работе сказано что "программа должна быть в виде функции" поэтому в отчете нужно выписать объявление функции, описание что она делает и возвращаемое значение С возвращаемым значением вроде как разобралась, а вот с объявлением функции проблема(((
0
M128K145
Эксперт С++
8288 / 3508 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
10.09.2009, 10:08 #9
valeriikozlov, clrscr() - это борландовская функция которая очищает экран. Аналог в MSVS и Dev-C++ -
C++
1
system("cls");
1
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
10.09.2009, 19:47  [ТС] #10
помогите пожалуйста, как разделить программу на main и отдельно функцию которая выполняет все вычисления? Помимо этого надо сделать так чтобы перед началом работы програмки можно было указать сколько чисел генерировать
0
M128K145
Эксперт С++
8288 / 3508 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
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;
}
1
Sweet Dream
1 / 1 / 0
Регистрация: 09.09.2009
Сообщений: 18
12.09.2009, 00:40  [ТС] #12
спасибо огромное за помощь))
0
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,370
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 суток
0
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? выводит на печать результат?
1
M128K145
Эксперт С++
8288 / 3508 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
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 - выводит на печать
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.09.2009, 20:46
Привет! Вот еще темы с ответами:

Генерация случайных чисел - C++
Мне нужно заполнить множество матриц числами 0 или 1. Для этого использую функцию rand. Но мне необходима совсем случайная...

Генерация случайных чисел - C++
Для генерации случайных чисел использую выражение: x = rand() % 4; Библиотеку &lt;cstdlib&gt; компилятор подключать не требует (VS12). ...

Генерация случайных чисел - C++
Помогите пожалуйста с этой программой, я ни как не могу понять как ее зделать. Написать программу, которая генерирует три...

Генерация случайных чисел - C++
Доброго времени суток ! Как генерировать случайное число например в диапазоне от 1 до 52 а потом исключить это число, и генерировать...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
15.09.2009, 20:46
Ответ Создать тему
Опции темы

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