Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.69/54: Рейтинг темы: голосов - 54, средняя оценка - 4.69
zambaldzr
1

В интервале от a до b найти число с наибольшим количеством делителей

26.09.2012, 22:46. Показов 10821. Ответов 35
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
a и b вводятся с клавиатуры,представить в виде функции
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
26.09.2012, 22:46
Ответы с готовыми решениями:

В заданном интервале найти число, с наибольшим количеством делителей
На вход программы подаются положительные числа a и b. Гарантируется, что а <= b. Найти число из...

Найти в диапазоне от M до N число с наибольшим количеством делителей. Функция: количество делителей заданного числа
Найти в диапазоне от M до N число с наибольшим количеством делителей. Функция: количество делителей...

Найти в диапазоне от M до N число с наибольшим количеством делителей.
Найти в диапазоне от M до N число с наибольшим количеством делителей. Функция: количество делителей...

Дано число P, нужно найти число от 1 до Р, с наибольшим количеством делителей
написал проггу, что не правильно уже 3 часа бьюсь... int p; int max=0,a = 0; ...

35
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 14:41 21
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от ValeryS Посмотреть сообщение
fnc и fnc1 менее секунды
fnc2 после 5 минут устал ждать и отрубил программу
Видите как важна оптимизация, если она возможна можете для наглядности еще алгоритм из поста 8 добавить
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 15:56 22
Цитата Сообщение от Thinker Посмотреть сообщение
Видите как важна оптимизация,
Кто бы спорил
я просто прикинул что если даже секунду проходит 100 000 000 итераций цикла (это слишком оптимистично)
то 3 алгоритм (не оптимизированный) будет продолжатся 10 000 секунд а это около 3 часов

Цитата Сообщение от Thinker Посмотреть сообщение
можете для наглядности еще алгоритм из поста 8 добавить
будет 5 000 секунд
слишком долго ждать, жизнь коротка
0
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 16:25 23
ValeryS, спасибо за код
сейчас попробую перебрать все для себя
и с математикой наконец разобраться
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 17:35 24
Zambal,
спасибо то не только мне а и Thinker, самый оптимальный код он предложил в 13 посте (2 листинг)
может можно еще как нибудь оптимизировать. но я не знаю как
0
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 18:11 25
как я понял,мой ход мыслей был правильный,но меня сбивало непонимание функций
теперь мучаюсь с массивом, нужно вывести несколько чисел, если у них одинаковое максимальное число делителей

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
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <windows.h>
int devident(int a, int b, int *pnum)
{
    int max = 0, m=0, d;
    int *num = new int[m];
    for (int n = a; n <= b; n++)
    {
        int count = 2;
        for  (d = 2; d * d < n; d++)
            count += ((n % d == 0) << 1);
                count += (d * d == n);
        if (count > max)
        {
            max = count;
            num[m] = n;
        }
    }
 
    if (pnum != NULL) *pnum = num[m];
 
    return max;
}
 
 
int main()
{
    int a = 0, b = 0, m = 0;
    int *num = new int[m];
    printf("a = "); scanf("%d",&a);
    printf("b = "); scanf("%d",&b);
 
    int max = devident(a,b, &num[m]);
    printf("number = %d devidents = %d\n",num[m], max);
 
    _getch();
    system("pause");
    return 0;
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 18:11 26
Thinker, вот как твою функцию компильнул VS2008
вообще ни одного ветвления
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
text:00401050 loc_401050:                             ; CODE XREF: _main+2Bj
.text:00401050                 mov     eax, 0F4240h
.text:00401055                 cdq
.text:00401056                 idiv    ecx
.text:00401058                 neg     edx
.text:0040105A                 sbb     edx, edx
.text:0040105C                 inc     ecx
.text:0040105D                 mov     eax, ecx
.text:0040105F                 imul    eax, ecx
.text:00401062                 inc     edx
.text:00401063                 cmp     eax, 0F4240h
.text:00401068                 lea     esi, [esi+edx*2]
.text:0040106B                 jl      short loc_401050
.text:0040106D                 mov     edx, ecx
.text:0040106F                 imul    edx, ecx
.text:00401072                 xor     eax, eax
.text:00401074                 cmp     edx, 0F4240h
.text:0040107A                 setz    al
.text:0040107D                 add     eax, esi
.text:0040107F                 mov     edi, eax
.
но это если аргумент int
но если long long
сразу пошли jz jnz....
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 18:30 27
Вот еще быстрее вариант
C++
1
2
3
4
5
6
7
8
9
10
11
unsigned long Count(unsigned long a)
{
   unsigned long i = 2, d = 1, count = 2;
   if (a == 1 || a == 2)
      return a;
   d += (a & 1);
   i += (a & 1);
   for(; i * i < a; i += d)
      count += (a % i == 0) << 1;
   return count + (i * i == a);
}
Такая функция числа от 1 до 1 000 000 обрабатывает за 2 сек.
1
Эксперт С++
261 / 191 / 10
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
27.09.2012, 19:48 28
Народ, не могу вьехать в определение кол-ва делителей.
Сколько делителей у числа 12 или 720 ?
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 20:10 29
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
числа 12
1 2 3 4 6 12 итого 6 делителей
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
или 720
лень мне сам считай

Добавлено через 1 минуту
прога показала 30 делителей по всем трем алгоритмам
0
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 21:12 30
ValeryS, что требуется изменить в коде,чтобы числа в массив записывались и выводились в строку.если имеют одинаковое кол-во делителей?
0
Модератор
Эксперт по электронике
8908 / 6677 / 918
Регистрация: 14.02.2011
Сообщений: 23,521
27.09.2012, 21:32 31
здесь я вижу такое решение
выделить нахождение общих делителей в отдельную функцию
в первом цикле ты ищешь число с максимальным количеством делителей
во втором цикле сравниваешь и выводишь на экран(без записи в массив)
например так fnc это функция нахождения общих делителей
MaxCount максимальное число общих делителей
C++
1
2
3
for(int i=a;i<=b;i++)
  if(MaxCount==fnc(i))
      printf ("%d %d \n",i MaxCount )
решение не оптимальное "в лоб" но самое простое
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
28.09.2012, 03:20 32
Вариант (при поиске в большом интервале будет самым быстрым из здесь приведенных):
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
unsigned long f(unsigned long a)
{
    if (a == 1 || a == 2)
      return a;
    unsigned long n=(unsigned long)sqrt((double)a), i, tmp=0, res;  
    while(a%2==0)
    {
        tmp++;
        a/=2;
    }
    res=tmp;
    for(i=3; i<=n && a>1; i+=2)
        if(a%i==0)
        {
            tmp=0;
            while(a%i==0)
            {
                tmp++;
                a/=i;
            }
            res=res+tmp+res*tmp;
        }
    if(a>1)
        res=res*2+1;
    return res+1;
}
2
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 14:26 33
Лучший ответ Сообщение было отмечено как решение

Решение

valeriikozlov, вот функция, которая работает быстрее, чем все предыдущие функции данного раздела, причем в разы
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
unsigned long Count(unsigned long a)
{
   unsigned long count = 1, k = 0, i;
   if (a == 1 || a == 2)
      return a;
   while ((a & 1) == 0)
   {
      k++;
      a >>= 1;
   }
   if (a == 1)
      return k + 1;
   else
      count = k + 1;
   for(i = 3; i*i <= a; i += 2)
   {
      k = 0;
      while(a % i == 0)
      {
         k++;
         a /= i;
      }
      count *= (k + 1);
   }
   if (a > 1)
      count <<= 1;
   return count;
}
Можно еще быстрее сделать.
3
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
28.09.2012, 17:53 34
Цитата Сообщение от Thinker Посмотреть сообщение
valeriikozlov, вот функция, которая работает быстрее, чем все предыдущие функции данного раздела
я хотел этот вариант тоже показать, но в следующем посте.

Цитата Сообщение от Thinker Посмотреть сообщение
Можно еще быстрее сделать.
А вот это уже интересно было бы увидеть.
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
28.09.2012, 18:24 35
Вы наверное у же видели вариант с дополнительной памятью
Быстрое нахождение количества делителей натурального числа
пока только в этом направлении вижу ускорение алгоритма. Хотелось бы, чтобы модераторы отнесли ту тему в большую коллекцию решенных задач , так как такая тема актуальна, часто возникает и очень удобно ее найти там будет, но они почему-то не хотят...

valeriikozlov, спасибо Вам за свой алгоритм, он натолкнул меня на мысль, что отбрасывать делители ( n /= i) эффективнее, что так и оказалось, поэтому алгоритм из поста 33 получился быстрым.
1
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
28.09.2012, 19:14 36
Цитата Сообщение от Thinker Посмотреть сообщение
Вы наверное у же видели вариант с дополнительной памятью
быстрое нахождение количества делителей натурального числа
нет не видел, только сейчас посмотрел.

Цитата Сообщение от Thinker Посмотреть сообщение
Хотелось бы, чтобы модераторы отнесли ту тему в большую коллекцию решенных задач , так как такая тема актуальна, часто возникает и очень удобно ее найти там будет, но они почему-то не хотят
Давайте вместе попросим. Я тоже прошу.


Цитата Сообщение от Thinker Посмотреть сообщение
спасибо Вам за свой алгоритм, он натолкнул меня на мысль, что отбрасывать делители ( n /= i) эффективнее, что так и оказалось, поэтому алгоритм из поста 33 получился быстрым.
Не за что.
1
28.09.2012, 19:14
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.09.2012, 19:14
Помогаю со студенческими работами здесь

Найти число с наибольшим количеством делителей из числового промежутка
Помогите решить задачу, пожалуйста, не понимаю как правильно ее реализовать Задан промежуток от...

Найти в диапазоне от M до N число с наибольшим количеством делителей. PHP
Есть форма, в которую мы вводим значения M и N. Ее я написал: &lt;html&gt; &lt;head&gt; &lt;/head&gt; &lt;body&gt;...

Дано n целых чисел. Найти среди них число с наибольшим количеством делителей
Дано n целых чисел.Найти среди них число с наибольшим количеством делителей.

Найти и вывести первое число в интервале a, b с количеством делителей равным c
Даны три натуральных числа a,b,c. Составить программу,которая находит и выводит первое число в...


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

Или воспользуйтесь поиском по форуму:
36
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru