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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.74
zambaldzr
Сообщений: n/a
#1

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

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

a и b вводятся с клавиатуры,представить в виде функции
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2012, 22:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос В интервале от a до b найти число с наибольшим количеством делителей (C++):

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

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

Дан одномерный целочисленный массив. Определить элемент с наибольшим количеством делителей - C++
Ребят, задача такая: "Дан одномерный целочисленный массив. Определить элемент с наибольшим количеством делителей." Помогите плиз...

Определить натуральное число не больше заданного n с наибольшим числом простых делителей - C++
Вот наткнулся на интересную задачку,ну,по карйней мере меня заинтересовала:good:,ну так вот : 1. Определить натурально число не больше...

Найти паралелограмм с наибольшим количеством точек - C++
Приветствую всех. Обращаюсь с помощью, так как эта программа уже выводит меня из себя. Задание состоит в следующем: "Даны N точек на...

Найти слово с наибольшим количеством гласных букв - C++
Гляньте что не так: #include <iostream> #include <string.h> #include <conio.h> using namespace std; void main(){ char...

35
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
27.09.2012, 12:42 #16
Цитата Сообщение от Thinker Посмотреть сообщение
внимательнее на for посмотрите, условие там d*d < n
пардон не заметил
просто на автомате подумал что вторая проверка в теле цикла
но тогда d нужно объявить за пределами цикла
нужно обговорить для начинающих
Цитата Сообщение от Thinker Посмотреть сообщение
C++
1
2
3
for (d = 2; d * d < n; d++)
 count += ((n % d == 0) << 1);
count += (d * d == n);
Вот это круто
вообще нет переходов
но боюсь не все поймут
да и явно привести надо буля к инту а то может не умножится
хотя не проверял верю на слово
0
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 12:47 #17
логические выражения типа (a < b) и т.д. приводятся к 0 или 1 в зависимости от истины, так что здесь все нормально
0
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
27.09.2012, 12:53 #18
Цитата Сообщение от Thinker Посмотреть сообщение
логические выражения типа (a < b) и т.д. приводятся к 0 или 1
это то я знаю , точнее приводятся false(0) и true (1)
я просто экспериментировал
C++
1
2
3
4
bool t=false;// t=0;
t++; // t= true =1 
t++; // t= true =1 
t++; // t= true =1
и никакой 2 (хотя она тоже true) не возникало
вот и возник вопрос
C++
1
int m=true<<1;
будет m равна 2 или нет (просто не проверял)
1
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 12:56 #19
Ну, в крайнем случае можно к типу int привести, это уже не страшно. Тоже не проверял еще
0
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
27.09.2012, 13:23 #20
Thinker,
проверил работает
причем сравнил три алгоритма (правда на глаз, точных замеров не делал)
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
#include "stdafx.h"
 int fnc(long long int n)
{
  long long int d; 
   int count=2;
    for (d = 2; d * d < n; d++)
     count += ((n % d == 0) << 1);
    count += (d * d == n);
 return count;
 }
 int fnc1(long long int n)
{
  long long int d; 
   int count=2;
 for (d = 2; d * d <= n; d++)
   {
      if(d *d== n)
        count++; 
     else  
      if ((n % d) == 0) 
            count+=2;
    }
 return count;
 }
int fnc2(long long int n)
{
   long long int d; 
   int count=0;
    for (d = 1; d <= n; d++)
     if(n % d == 0) 
         count++;
    return count;
 }
int _tmain(int argc, _TCHAR* argv[])
{
   int k= fnc(1000000000000);
   int m=fnc1(1000000000000);
   int p=fnc2(1000000000000);
   printf("%d %d %d",k,m,p);
    return 0;
}
fnc и fnc1 менее секунды
fnc2 после 5 минут устал ждать и отрубил программу
1
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.09.2012, 14:41 #21
Цитата Сообщение от ValeryS Посмотреть сообщение
fnc и fnc1 менее секунды
fnc2 после 5 минут устал ждать и отрубил программу
Видите как важна оптимизация, если она возможна можете для наглядности еще алгоритм из поста 8 добавить
0
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
27.09.2012, 15:56 #22
Цитата Сообщение от Thinker Посмотреть сообщение
Видите как важна оптимизация,
Кто бы спорил
я просто прикинул что если даже секунду проходит 100 000 000 итераций цикла (это слишком оптимистично)
то 3 алгоритм (не оптимизированный) будет продолжатся 10 000 секунд а это около 3 часов

Цитата Сообщение от Thinker Посмотреть сообщение
можете для наглядности еще алгоритм из поста 8 добавить
будет 5 000 секунд
слишком долго ждать, жизнь коротка
0
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 16:25 #23
ValeryS, спасибо за код
сейчас попробую перебрать все для себя
и с математикой наконец разобраться
0
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
27.09.2012, 17:35 #24
Zambal,
спасибо то не только мне а и Thinker, самый оптимальный код он предложил в 13 посте (2 листинг)
может можно еще как нибудь оптимизировать. но я не знаю как
0
Zambal
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
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
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
Thinker
Эксперт С++
4226 / 2200 / 150
Регистрация: 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
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
27.09.2012, 19:48 #28
Народ, не могу вьехать в определение кол-ва делителей.
Сколько делителей у числа 12 или 720 ?
0
ValeryS
Модератор
6654 / 5063 / 470
Регистрация: 14.02.2011
Сообщений: 16,930
27.09.2012, 20:10 #29
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
числа 12
1 2 3 4 6 12 итого 6 делителей
Цитата Сообщение от Andrew_Lvov Посмотреть сообщение
или 720
лень мне сам считай

Добавлено через 1 минуту
прога показала 30 делителей по всем трем алгоритмам
0
Zambal
83 / 3 / 1
Регистрация: 14.11.2011
Сообщений: 68
27.09.2012, 21:12 #30
ValeryS, что требуется изменить в коде,чтобы числа в массив записывались и выводились в строку.если имеют одинаковое кол-во делителей?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2012, 21:12
Привет! Вот еще темы с ответами:

Найти слова с наибольшим количеством гласных букв - C++
Вводится строка слов, написанных латинскими буквами. Необходимо вывести слова(-о), в которых содержится наибольшее кол-во гласных букв( e y...

Найти столбец матрицы с наибольшим количеством нулей - C++
Здравствуйте, нужна срочно помощь с двумя программами, а то я в программировании - ноль=/ Первую программу нужно сделать со статическими...

Найти столбец матрицы с наибольшим количеством элементов кратных 5 - C++
Найти номер столбца массива размером МхN, в котором находится наибольшее количество элементов, кратных 5. Элементы задаются датчиком...

Найти в двумерном массиве строку с наибольшим количеством одинаковых элементов - C++
Помогите понять как работать с двумерными массивами. Условие задания: Найти строку с наибольшим количеством одинаковых элементов. Вот что я...


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

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

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