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

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

Войти
Регистрация
Восстановить пароль
 
kiborg_18
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
#1

Единицы - C++

03.04.2011, 17:17. Просмотров 938. Ответов 3
Метки нет (Все метки)

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

В арифметическом выражении разрешается использовать число 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;
  }
}
Может где-то ошибка?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2011, 17:17     Единицы
Посмотрите здесь:

Дано натуральное число n. Отбросить в нем все цифры, стоящие правее самой правой единицы либо оставить число без изменений, если единицы в нем нет C++
C++ Определяет единицы массы в кг
C++ Распознать нули и единицы
C++ Древнерусские Неметрические единицы длины
C++ Единицы
Единицы массы C++
C++ факториал с точностью до единицы
Округление float до единицы C++
C++ Разделение двузначного числа на десятки и единицы
Степень минус единицы C++
C++ Заполнить массив единицами и минус единицами и поменять единицы и минус единицы местами
Шаблоны и единицы трансляции C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ping_rulezzz
26 / 26 / 4
Регистрация: 18.02.2011
Сообщений: 51
03.04.2011, 22:00     Единицы #2
при каких значениях у вас валится программа? т.к. прокрутил цикл от 1 и до 5000 для переменной "a" - всё стабильно - не знаю на сколько корректные значения выводит, но нигде не крешится.
Единственное - добавьте return 0; в конец функции main()
Somebody
2777 / 1591 / 142
Регистрация: 03.12.2007
Сообщений: 4,169
Завершенные тесты: 1
03.04.2011, 22:52     Единицы #3
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
4 / 4 / 0
Регистрация: 21.02.2011
Сообщений: 61
04.04.2011, 16:50  [ТС]     Единицы #4
Цитата Сообщение от Somebody Посмотреть сообщение
45 => 11
46 => 13
Хотя 46 = 45 + 1. А простые числа тут вообще, по-моему, не в тему.
Большое спасибо, не знаю почему такая ошибка, но в целом мои рассуждения должны были быть верны. Вот смотри, числа 1,2,3,5 включают в себя столько единиц сколько они сами. Значит мне надо представить число в виде суммы произведения этих чисел.
А вот число 45 включает в себя 11 единиц, тут я не учёл что 46 это разложение 45+1, хотя 25 включает 10 единиц, и 26 тоже 10, я не учёл исключений(((
А можешь мне порекомендовать какую нибудь книжку для динамического программирования, остальные я более или менее секу, вот на этих и на графах признаться я слабоват...
Yandex
Объявления
04.04.2011, 16:50     Единицы
Ответ Создать тему
Опции темы

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