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

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

Восстановить пароль Регистрация
 
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 21:38     По заданному числу n вычислить минимальную сумму чисел #1
Нужно по заданному числу 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++
Определить количество чисел из промежутка от X до Y, кратных заданному числу C++
2. Составить программу для определения количества трехзначных чисел, кратных заданному числу C++
C++ написать и протестировать функцию которая по заданному натуральному числу определяет количество цифр в нем и их сумму
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
darkknight2008
 Аватар для darkknight2008
61 / 61 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 21:46     По заданному числу n вычислить минимальную сумму чисел #2
Первое, что пришло в голову - это найти делители числа n. Перебором произведений этих делителей можно составить все числа для которых n - это НОК. А реализация.... смотри форум, темы по поиску делителей уже были.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 21:50  [ТС]     По заданному числу n вычислить минимальную сумму чисел #3
Я пытался тоже делать через делители, и наверное это правильно, но у меня не получилось.
miriganua
129 / 100 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.03.2012, 21:51     По заданному числу n вычислить минимальную сумму чисел #4
Хочу уточнить правильно ли я понял задание:
если n=12, то мы должны найти 3 + 2
если n=20, то мы должны найти 2 + 5
если n=13?
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 22:05  [ТС]     По заданному числу n вычислить минимальную сумму чисел #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
 Аватар для darkknight2008
61 / 61 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 22:22     По заданному числу n вычислить минимальную сумму чисел #6
Если моя интуиция не подвирает. То задачу сводится к поиску суммы всех простых делителей числа. вроде пока опровержения не нашел. И как я понял нужно учитывать и повторение делителей.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
07.03.2012, 22:24  [ТС]     По заданному числу n вычислить минимальную сумму чисел #7
Вы можете это написать кодом? я пока очень слаб в понимании что нужно делать...
darkknight2008
 Аватар для darkknight2008
61 / 61 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 22:48     По заданному числу n вычислить минимальную сумму чисел #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
129 / 100 / 4
Регистрация: 05.02.2012
Сообщений: 241
07.03.2012, 22:50     По заданному числу n вычислить минимальную сумму чисел #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
 Аватар для darkknight2008
61 / 61 / 6
Регистрация: 16.10.2011
Сообщений: 200
07.03.2012, 23:06     По заданному числу n вычислить минимальную сумму чисел #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  [ТС]     По заданному числу n вычислить минимальную сумму чисел #11
Эту задачу нужно делать непременно как-то через НОК. Только вот как...
darkknight2008
 Аватар для darkknight2008
61 / 61 / 6
Регистрация: 16.10.2011
Сообщений: 200
08.03.2012, 00:25     По заданному числу n вычислить минимальную сумму чисел #12
"непременно как-то через НОК" Расплывчато... Выпиши чисел так 20 - никакой зависимости не прослеживается, так что врятли получится что-то подобрать.
Джон
0 / 0 / 0
Регистрация: 06.03.2012
Сообщений: 40
08.03.2012, 02:15  [ТС]     По заданному числу n вычислить минимальную сумму чисел #13
Так я это говорю не просто так. Эта задача из специальной темы про НОК

Добавлено через 1 час 30 минут
Я понял что надо сделать. Нужно только это реализовать. Сначала раскладываем число на простые множители. Если это число представляется в виде p1^k1, то ответом будет n+1, если же p1^k1*...*pn^kn, то ответом будет сумма этих чисел. Кстати,, вот сама задачаhttp://www.e-olimp.com.ua/problems/1246
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 03:24     По заданному числу n вычислить минимальную сумму чисел #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  [ТС]     По заданному числу n вычислить минимальную сумму чисел #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, 13:01     По заданному числу n вычислить минимальную сумму чисел
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.03.2012, 13:01     По заданному числу n вычислить минимальную сумму чисел #16
Цитата Сообщение от Джон Посмотреть сообщение
Это типа для условия, что у нас число не выше 2^31-1, и это нужно обязательно задать?
Это типа вот для чего, товарищ: по условию n может быть 2^31-1, а так как 2^31-1 является простым числом, то ответ должен быть: 2^31. Так как 2^31 не укладывается в int, то можно было воспользоваться long long или для этого случая сделать то что сделал я.
Yandex
Объявления
08.03.2012, 13:01     По заданному числу n вычислить минимальную сумму чисел
Ответ Создать тему
Опции темы

Текущее время: 01:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru