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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.85
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
#1

МНОЖИТЕЛИ - C++

18.11.2010, 16:30. Просмотров 1635. Ответов 26
Метки нет (Все метки)

Какое минимальное число можно представить как произведение AxB ровно K способами.
AxB и ВxА считаются одним способом. К <= 50.
Пример:
вводится число К:
4
ответ:
24
1*24; 2*12; 3*8; 4*6; -----> 4 способа

Добавлено через 4 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int main()
{
   int n = 1; // с какого числа начинаем
   int kF;    //найденое количество делителей
   int k;
   cin >> k; //количество способов
   while (1)
   {
      int i;
      kF = 0;
      for (i = 1; (i*i) <= n; i++)
            if (n%i == 0) kF++;   //находим делители
      if (kF == k) {cout << n << endl; break;} //если количество
      // делителей совпадает с нужным - выходим из цикла
      n++; // иначе переходим к следующему числу
   }
   cout << n << endl;
   return 0;
}
вот такое написал я ...
но для чисел К =37, 46, 47, 31 - решение найти не удалось
1
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.11.2010, 16:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос МНОЖИТЕЛИ (C++):

Множители - C++
Здравствуйте! Друзья, помогите пожалуйста сделать не очень сложную ( для вас задачку) буду очень признателен ! Огромное спасибо! Дано...

Множители - C++
Дано количество способов разложить число на множители. Нужно узнать это число (наименьшее из них). Я использовал перебор чисел, для каждого...

Протые множители - C++
Помогите решить задачу Задача: разложить данное число на простые множители

Разложить на простые множители - C++
разложить целое число на простые множители (код на си)

Разложение числа на множители - C++
var s1,s2,n: longint; f: integer; begin write('vvedite natural chislo '); readln(n); f:=0; s1:=1; ...

Разложение в простые множители - C++
Дано натуральное число n. Требуется найти его разложение на простые множители. Формат выходных данных Требуется вывести строго...

26
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
22.11.2010, 19:39 #16
Цитата Сообщение от Mayonez Посмотреть сообщение
решение существует но очень большое число или ...?
Мало того, существует как минимум два решения! valeriikozlov, и я Вам их озвучили. Другое дело, что так не самые маленькие из возможных чисел получаются, но делящиеся без остатка на нужное количество делителей. Кстати, программа, которую я написал, тоже не самое меньшее из возможных чисел выдаёт...

Добавлено через 59 секунд
Цитата Сообщение от valeriikozlov Посмотреть сообщение
я думаю решение найдем обязательно
ага... я уже тетрадку целую в 18 листов исписал - пока фигня какая-то получается, но чувствую, что где-то рядом...
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:24 #17
Мало того, существует как минимум два решения!
На самом деле решений для каждого К бесконечно... То что я привел для степеней 2, точно так же распостраняется для степеней любого простого числа.

Цитата Сообщение от easybudda Посмотреть сообщение
Кстати, программа, которую я написал, тоже не самое меньшее из возможных чисел выдаёт...
Я знаю.

На самом деле решение есть, а это самое главное. Осталось "пустяк" - найти его.
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
22.11.2010, 20:45 #18
Я что-то не пойму, разве количество делителей равно количеству способов? Что-то не въеду никак.
Пример:
вводится число К:
4
ответ:
24
1*24; 2*12; 3*8; 4*6; -----> 4 способа
4 способа,а делителей сколько? 8? или тоже четыре? Я насчитал 8,вот и не пойму. Или имеется ввиду простые множители? Тогда их три: 1,2,3. Всех остальных участников этих умножений в примере можно получить с помощью простых.
Автор,поясните.
Или я что-то недопонял,как всегда,или у автора ошибка тут
C++
1
 if (kF/2 == k) {cout << n << endl; break;} //если количество
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)

И ещё один момент: Если i увеличиваем до корня числа,то как мы найдём множитель 24 в случае,когда n==24? (как раз в случае приведённого примера). Поэтому проверять нужно, наверное, до самого числа,и делать ещё один вложенный цикл,отметая повторения,или что-то в этом духе. Или я опять ошибся
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
22.11.2010, 20:50 #19
#pragma, Из условия:
AxB и ВxА считаются одним способом.
Значит то что Вы насчитали 8 делителей это хорошо и правильно - поэтому К равно 4.

Добавлено через 1 минуту
Цитата Сообщение от #pragma Посмотреть сообщение
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)
Цитата Сообщение от Mayonez Посмотреть сообщение
Какое минимальное число можно представить как произведение AxB ровно K способами.
К может быть и нечетным числом
0
#pragma
Временно недоступен
954 / 225 / 6
Регистрация: 12.04.2009
Сообщений: 921
22.11.2010, 21:15 #20
Цитата Сообщение от valeriikozlov Посмотреть сообщение
А на два делить нужно поскольку количество множителей всегда кратно двум согласно условию (участие одного и того же элемента в разных перестановках исключено)
Какое минимальное число можно представить как произведение AxB ровно K способами.
#pragma,
К может быть и нечетным числом
Не вижу противоречия между двумя Вами приведёнными предложениями,так как "количество способов" != "количеству множителей" а автор в своём коде сравнивает их напрямую.
Ладно, спорить не буду, может, я прогнал просто

Добавлено через 12 минут
поправка: "количество способов" != "количеству простых делителей" - вот их и сравнивает автор.
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
24.11.2010, 17:13  [ТС] #21
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от #pragma Посмотреть сообщение
количество способов" != "количеству множителей"
количество способов равно количеству множителей/2 и в своем примере я ищу делители только до корня из н, тоесть ровно половину, а потом и сравниваю их
Цитата Сообщение от #pragma Посмотреть сообщение
"количеству простых делителей"
я ищу ВСЕ делители не только простые
2
easybudda
Модератор
Эксперт CЭксперт С++
9695 / 5645 / 963
Регистрация: 25.07.2009
Сообщений: 10,850
27.11.2010, 23:03 #22
"Я думал, думал, я всё понял!"(с)
Вот так 50 уникальных делителей находит
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
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
 
int main(void){
    uint64_t c; /* искомое число */
    int k, i; /* количество уникальных делителей, счётчик циклов */
    uint64_t * div; /* массив делителей размером k + 1 */
    
    printf("k = ");
    if ( scanf("%d", &k) != 1 ){
        fprintf(stderr, "wrong input!\n");
        exit(1);
    }
    if ( k < 4 ){
        printf("too simple!\n");
        exit(1);
    }
    
    if ( ( div = (uint64_t*)malloc(sizeof(uint64_t) * (k + 1)) ) == NULL ){
        fprintf(stderr, "memory error!\n");
        exit(1);
    }
    
    div[0] = 1;
    div[1] = 2;
    div[2] = 3;
    for ( i = 3; i < (k + 1); ++i )
        div[i] = div[i-2] * 2;
    
    c = div[k] * div[k-1];
    for ( i = 0; i < k; ++i )
        printf("#%d:\t%llu X %llu = %llu\n", i + 1, div[i], c / div[i], c);
    
    free(div);
    exit(0);
}
мало того - до 64 досчитало...
для случая k < 4 сделать не сложно (намекну - при к = 3 с = 18)

Добавлено через 1 час 1 минуту
и снова облом - не самое маленькое число находится (спасибо, valeriikozlov)... Но прогресс на лицо, будем дальше думать...
1
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
28.11.2010, 00:17 #23
Mayonez, Вы ссылку на тестирующую систему можете дать, которая принимает эту задачу? Или ее не существует?
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.12.2010, 12:39 #24
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
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
#include "math.h"
#include "stdio.h"
#include <iostream>
using namespace std;
int mas_p[15], i_mas_p=0, mas[50][15], mas_temp[15], mas_temp_res[15];
bool pr(int a)
{
    if(a==2)
        return true;
    if(a%2==0)
        return false;
    for(int i=3; i<=(int)sqrt((double)a); i+=2)
        if(a%i==0)
            return false;
    return true;
}
 
void ras(int a)
{
    int i, j, y, fl=0;
    for(i=0; i<15; i++)
        if(mas_temp[i]%2==1)
            fl=1;
    if(fl==0) a++;
    fl=0;
    for(i=0; i<15; i++)
        mas_temp_res[i]=0;
    mas_temp_res[0]=1;
    for(i=0; i<15; i++)
    {
        for(j=0; j<mas_temp[i]; j++)
        {
            for(y=0; y<15; y++)
                mas_temp_res[y]*=mas_p[i];
            for(y=0; y<14; y++)
                if(mas_temp_res[y]>999)
                {
                    mas_temp_res[y+1]+=mas_temp_res[y]/1000;
                    mas_temp_res[y]%=1000;
                }
        }
    }
    for(i=14; fl==0 && i>=0; i--)
    {
        if(mas_temp_res[i]<mas[a-1][i])
            fl=1;
        if(mas_temp_res[i]>mas[a-1][i])
            fl=2;
    }
    if(fl==1)
    {
        for(i=0; i<15; i++)
            mas[a-1][i]=mas_temp_res[i];
    }
}       
 
 
void gen(int max, int tv, int i_p, int kv, bool fl)
{
    if(!fl)
    {
        mas_temp[1]++;
        gen(max, 2*tv+1, 1, tv, true);
        mas_temp[1]--;
    }
    else
    {
        if((tv+1)/2<=50)
            ras((tv+1)/2);
        if(tv+1<=50)
        {
            mas_temp[i_p+1]++;
            gen(max, 2*tv+1, i_p+1, tv, true);
            mas_temp[i_p+1]--;
        }
        if(mas_temp[i_p]<max && (tv+kv+1)/2<=50)
        {
            mas_temp[i_p]++;
            gen(max, tv+kv+1, i_p, kv, true);
            mas_temp[i_p]--;
        }
        else
            return;
    }
}
 
int main()
{
    int i, j;
    for(i=2; i<50; i++)
        if(pr(i))
            mas_p[i_mas_p++]=i;
    mas[0][0]=1;
    for(i=1; i<50; i++)
    {
        for(j=0; j<15; j++)
            mas[i][j]=mas[i-1][j]*4;
        for(int j=0; j<14; j++)
        if(mas[i][j]>999)
        {
            mas[i][j+1]+=mas[i][j]/1000;
            mas[i][j]%=1000;
        }
    }
    // 
    mas_temp[0]=0;
    for(i=1; i<98; i++)
    {
        mas_temp[0]++;
        gen(i, i, 0, i, false);
    }
    //
    for(i=0; i<50; i++)
    {
        bool fl=true;
        printf("K= %d  ", i+1);
        for(j=14; j>=0; j--)
        {
            if(!fl)
                printf("%03d", mas[i][j]);
            if(fl && mas[i][j]!=0)
            {
                fl=false;
                printf("%d", mas[i][j]);
            }
        }
        printf("\n");
    }
   return 0;
}
Mayonez, Проверил заодно и вашу программу. Считает она оказывается для К=46, только немного долго, но быстрее чем для К=43. Остальные значения: К =37, 47, 31 сами поймете почему не считала.
1
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
04.12.2010, 18:45  [ТС] #25
valeriikozlov, за каким принципом работает программа?
сразу что-то не очень понятно
0
valeriikozlov
Эксперт С++
4673 / 2499 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.12.2010, 19:46 #26
Цитата Сообщение от Mayonez Посмотреть сообщение
valeriikozlov, за каким принципом работает программа?
сразу что-то не очень понятно
Если честно, то и мне не очень понятно(шучу )
Давайте сначало совсем без кода алгоритм объясню, потом понятней будет.
Здесь немного ДП и немного комбинаторики. Для начала заполняем массив mas[][] значениями степени 2 как написал в посте 11.
Далее рассматриваем числа произведения простых чисел. Смысл здесь такой, например К для числа 2*2*13*13 будет равно К для числа 2*2*3*3. Но число 2*2*3*3 заведомо меньше, чем число 2*2*13*13.
Вот по этому смыслу мы и перебираем все варианты наборов простых чисел, вычисляя их произведение (с использованием длинной арифметики), а также вычисляя число К для этого набора (и сравниваем с уже имеющимся числом для данного К).
Например есть набор простых чисел 2 2 2 3, то из этого набора родятся такие наборы чисел:
2 2 2 3 5
2 2 2 3 3

Добавлено через 13 минут
Mayonez, Дальше продолжать?
1
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
04.12.2010, 19:55  [ТС] #27
Цитата Сообщение от valeriikozlov Посмотреть сообщение
и мне не очень понятно

Цитата Сообщение от valeriikozlov Посмотреть сообщение
Mayonez, Дальше продолжать?
нет, спасибо большое за помощь
0
04.12.2010, 19:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2010, 19:55
Привет! Вот еще темы с ответами:

Разложение на простые множители* - C++
Привет всем, помогите решить, если можно с комментариями что и как, буду очень благодарен, а то у нас курс как-то слишком быстро вперед...

Разделить число на множители - C++
Нужно составить программу, в которой ты вводиш натуральное число, а она, если возможно, делит его на простые множители, тоесть 24=2*2*2*3...

Определить простые множители - C++
Задание: Составить программу определения, является ли данное число простым. Если число не является простым, то определить все его простые...

Разложить число на простые множители - C++
Дано натуральное число n. Напечатать разложение этого числа на простые множители. Реализовать два варианта: 1) каждый простой множитель...


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

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Опции темы

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