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

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

Войти
Регистрация
Восстановить пароль
 
 
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
#1

По заданному числу n вычислить минимальную сумму чисел - C++

07.03.2012, 21:38. Просмотров 916. Ответов 15
Метки нет (Все метки)

Нужно по заданному числу n вычислить МИНИМАЛЬНУЮ сумму чисел, для которых n - наименьшее общее кратное. Бьюсь уже третий день над ней. Никто так и не помог с реализацией кода(((

Пример: Число 12. Для него сумма 3 и 4=7 - минимальная, так при 4, 6 - будет сумма уже 10. А при других числах 12 будет уже не НОК.
Число 30 - для него подходящая минимальная сумма 2 3 5 - 10. Для 2 3 5 , 30 - НОК.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.03.2012, 21:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос По заданному числу n вычислить минимальную сумму чисел (C++):

Вычислить сумму членов последовательности натуральных чисел, кратных и не кратных заданному числу - C++
Дана последовательность натуральных чилел А. Вычислить сумму членов последовательности, кратных и не кратных d. Значения членов...

Найти сумму натуральных чисел, предшествующих заданному числу a - C++
Найти сумму натуральных чисел, предшествующих заданному числу a.

Вычислить сумму элементов массива у которых сумма индексов равна заданному числу - C++
Массив A содержит действительные числа и задается пользователем с клавиатуры вместе с размерностью . Пользователь задает целое число k....

Вычислить сумму чисел, принадлежащих заданному промежутку и лежащих на главной диагонали и выше ее - C++
Задана квадратная матрица порядка N. Вычислить сумму чисел, принадлежащих промежутку [K,L) и лежащих на главной диагонали и выше ее. ...

По заданному числу определить наименьшую сумму его делителей - C++
Есть у нас число. Допустим 12. Оно является НОК чисел 6 и 4, а также 6 4 1, 6 4 1 3 и т.д. Задача состоит в том, что нужно вывести...

Найти сумму элементов, кратных удвоенному заданному числу - C++
1-Заполнить массив из 12 элементов (случайным образом) вещественными числами в диапозоне от (-50,50). Найти сумму элементов, кратных...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 21:46 #2
Первое, что пришло в голову - это найти делители числа n. Перебором произведений этих делителей можно составить все числа для которых n - это НОК. А реализация.... смотри форум, темы по поиску делителей уже были.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 21:50  [ТС] #3
Я пытался тоже делать через делители, и наверное это правильно, но у меня не получилось.
miriganua
131 / 102 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.03.2012, 21:51 #4
Хочу уточнить правильно ли я понял задание:
если n=12, то мы должны найти 3 + 2
если n=20, то мы должны найти 2 + 5
если n=13?
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 22:05  [ТС] #5
Нет-нет. Если 12, то 3+4, поскольку для 3 и 2 НОК - 6. Если 20, то 5+4. То есть сумма таких чисел, для которых входное число n - НОК. А если простое число, то разумеется оно же самое +1. То есть для 13 - ответ 14 , для 1 - ответ 2, для 2 - ответ 3 , для 3 - 4 и т.д.
И еще такой момент: если 30, то не 5+6, а 5+3+2. Вроде бы одно и то же, но сумма во втором случае у нас будет меньше на 1, чем в первом, то есть МИНИМАЛЬНАЯ. Вот из-за этих мелких деталей и не могу решить задачу. Помогите
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 22:22 #6
Если моя интуиция не подвирает. То задачу сводится к поиску суммы всех простых делителей числа. вроде пока опровержения не нашел. И как я понял нужно учитывать и повторение делителей.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 22:24  [ТС] #7
Вы можете это написать кодом? я пока очень слаб в понимании что нужно делать...
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 22:48 #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int N; // Наше число
int sum = 0; // Наша сумма
 
int inc = N; // Берем копию нашего числа.
int i = 2;
while (inc != 1)
  if (inc % i == 0) // Проверяем делитель ли.
  {
    sum += i;
    inc /= i;
  }
  else // Если не делитель, то идем дальше.
    i++;
// А дальше выводим сумму
Проверь, я не совсем уверен в этом каламбуре. Но на первый взгляд все ок.
miriganua
131 / 102 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.03.2012, 22:50 #9
Вот мой вариант, не думаю, что он самый лучший, но вроде работает - проверь:

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
#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    cout << "Enter number:";
    cin >> n;
 
    int* arr = new int[n + 1];
    for (int i = 0; i < n + 1; i++)
    {
        arr[i] = i;
    }
 
 
    for (int i = 2; i < n; i++)
    {
        if (i == 0)
        {
            continue;
        }
        for (int j = i + i; j < n; j += i)
        {
            arr[j] = 0;
        }
    }
 
    int sum = 0;
    for (int i = 2; i < n; i++)
    {
        if (arr[i] != 0 && n % arr[i] == 0)
        {
            sum += arr[i];
        }
    }
    if (sum == 0)
    {
        sum = arr[1] + arr[n];
    }
    
    cout << "Sum:" << sum << '\n';
    return 0;
}
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 23:06 #10

Не по теме:

Игорь Миронюк, ну ты и монстра родил. Но идея вполне работоспособная))



Добавлено через 3 минуты
Вопросик, что должно выводить если число n = 17?

Добавлено через 1 минуту
По идее результат у нас должен быть 18? Тогда к моему коду надо приписать в конец
C++
1
2
if (sum == 0)
  sum = 1 + N;
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 23:43  [ТС] #11
Эту задачу нужно делать непременно как-то через НОК. Только вот как...
darkknight2008
62 / 62 / 6
Регистрация: 16.10.2011
Сообщений: 200
08.03.2012, 00:25 #12
"непременно как-то через НОК" Расплывчато... Выпиши чисел так 20 - никакой зависимости не прослеживается, так что врятли получится что-то подобрать.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
08.03.2012, 02:15  [ТС] #13
Так я это говорю не просто так. Эта задача из специальной темы про НОК

Добавлено через 1 час 30 минут
Я понял что надо сделать. Нужно только это реализовать. Сначала раскладываем число на простые множители. Если это число представляется в виде p1^k1, то ответом будет n+1, если же p1^k1*...*pn^kn, то ответом будет сумма этих чисел. Кстати,, вот сама задачаhttp://www.e-olimp.com.ua/problems/1246
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 03:24 #14
Сдавайте:
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
#include <stdio.h>
#include <math.h>
int main()
{
  int n, sum, i=1, tmp, j, n1, fl;  
  while(true)
  {
      scanf("%d", &n);
      if(n==0)
          break;
      sum=0;
      fl=0;
      if(n==1)
          printf("Case %d: %d\n", i, 2);
      else
      {
          if(n==2147483647)
              printf("Case %d: 2147483648\n", i);
          else
          {
          n1=n;
          for(j=2; j<=(int)sqrt((double)n1); j++)
              if(n%j==0)
              {
                  fl++;
                  tmp=1;
                  while(n%j==0)
                  {
                      tmp*=j;
                      n/=j;
                  }
                  sum+=tmp;
              }
          if(n==1)
          {
              if(fl==1)
                  printf("Case %d: %d\n", i, sum+1);
              else
                  printf("Case %d: %d\n", i, sum);
          }
          else
          {
              if(fl>0)
                  printf("Case %d: %d\n", i, sum+n);          
              else
                  printf("Case %d: %d\n", i, sum+n+1);  
          }
          }
      }
      i++;
  } 
        return 0;
}
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
08.03.2012, 12:55  [ТС] #15
Огоромное Вам спасибо, товарищ!! Очень помогли, а главное, код понятный и в нем легко разобраться (что немаловажно).Полагаю, Вы в свое время эту задачу тоже отправляли на тест, поскольку не мог не заметить этой строки
Цитата Сообщение от valeriikozlov Посмотреть сообщение
f(n==2147483647)
*printf("Case %d: 2147483648\n", i);
Это типа для условия, что у нас число не выше 2^31-1, и это нужно обязательно задать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.03.2012, 12:55
Привет! Вот еще темы с ответами:

Посчитать сумму всех элементов, кратных заданному числу - C++
Дан массив a из n целых чисел. Требуется посчитать сумму всех элементов, кратных заданному числу x.

Найти сумму всех элементов, кратных заданному числу - C++
Здравствуйте много уважаемые форумчане!!!Помогите решить задачу на языке С++ ..... Дан массив целых чисел. Найти сумму всех элементов,...

По графику функции y=f(x) и заданному вещественному числу a вычислить f(а) - C++
Дано вещественное число а. Для функции y=f(x), график которой приведен ниже вычислить f(а)

По заданному натуральному числу определить количество цифр в нём и их сумму - C++
ПЛЗ,помогите:help: Написать и протестировать функцию, которая по заданному натуральному числу определяет количество цифр в нём и их...


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

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

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