Единицы

@kiborg_18 · Регистрация: 21.02.2011

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста с решением задачи

В арифметическом выражении разрешается использовать число 1, операции сложения, умножения и скобки.
Какое наименьшее количество единиц нужно использовать, чтобы получить заданное натуральное число n?
Технические условия
Входные данные
Одно число n. 1 ≤ n ≤ 5000.
Выходные данные
Искомое количество единиц.
Пример входных данных
7
Пример выходных данных
6

Набросал код, но программа валится на 3 тестах.

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
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
 
int rez=0;
void prime_eratosfen(int *mas, int n); 
void search_primes(int a,int *mas, int n);
int main()
{
 int n=5001,*mas=NULL,a;
 cin >> a;
 rez=0;
 if (a==1) { cout << 1 << endl; return 0; }
 mas=(int*)malloc(n*sizeof(int));
 prime_eratosfen(mas,n); //Определяем все простые числа до заданного
 search_primes(a,mas,n);
 cout << rez << endl;
}
 
void prime_eratosfen(int *mas, int n)
{
 int i,j;
 for (i=0; i<n; i++) mas[i]=i;
 mas[1]=0;
 for (j=2; j<n; j++)
  {
   if (mas[j]!=0)
    {
     for (i=2*j; i<n; i+=j)
      {
       mas[i]=0;
      }
    }
  }
}
 
void search_primes(int a,int *mas, int n)
{
 int j;
 while (1)
  {
   if (mas[a]!=0 && a!=2 && a!=3 && a!=5) { rez++; a--; }
   else
    {
     if (a%2==0) { a/=2; rez+=2; }
     else if (a%3==0) { a/=3; rez+=3; }
     else if (a%5==0) { a/=5; rez+=5; }
     else
      {
       for (j=7; j<n; j++)
        {
         if (mas[j]!=0)
          {
           if (a%mas[j]==0)
            {
             a/=mas[j];
             search_primes(mas[j],mas,n);
            }
          }
        }
      }
    }
   if (a==1) break;
  }
}

Может где-то ошибка?

@ping_rulezzz · 03.04.2011, 22:00

при каких значениях у вас валится программа? т.к. прокрутил цикл от 1 и до 5000 для переменной "a" - всё стабильно - не знаю на сколько корректные значения выводит, но нигде не крешится.
Единственное - добавьте return 0; в конец функции main()

@Somebody · 03.04.2011, 22:52

45 => 11
46 => 13
Хотя 46 = 45 + 1. А простые числа тут вообще, по-моему, не в тему.

Мой вариант

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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int m = 5001;
 
int main()
{
    int n;
    cin >> n;
 
    int a[m + 1];
    for (int i = 0; i <= m; i++)
        a[i] = m;
    a[1] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 1, k; (k = i + j) <= n; j++)
            a[k] = min(a[k], a[i] + a[j]);
        for (int j = 1, k; (k = i * j) <= n; j++)
            a[k] = min(a[k], a[i] + a[j]);
    }
 
    cout << a[n] << endl;
}

@kiborg_18 · 04.04.2011, 16:50 **[ТС]**

Сообщение от Somebody

45 => 11
46 => 13
Хотя 46 = 45 + 1. А простые числа тут вообще, по-моему, не в тему.

Большое спасибо, не знаю почему такая ошибка, но в целом мои рассуждения должны были быть верны. Вот смотри, числа 1,2,3,5 включают в себя столько единиц сколько они сами. Значит мне надо представить число в виде суммы произведения этих чисел.
А вот число 45 включает в себя 11 единиц, тут я не учёл что 46 это разложение 45+1, хотя 25 включает 10 единиц, и 26 тоже 10, я не учёл исключений(((
А можешь мне порекомендовать какую нибудь книжку для динамического программирования, остальные я более или менее секу, вот на этих и на графах признаться я слабоват...

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@ping_rulezzz 26 / 26 / 12 Регистрация: 18.02.2011 Сообщений: 51
	03.04.2011, 22:00
	при каких значениях у вас валится программа? т.к. прокрутил цикл от 1 и до 5000 для переменной "a" - всё стабильно - не знаю на сколько корректные значения выводит, но нигде не крешится. Единственное - добавьте return 0; в конец функции main() 0