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

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

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

Единицы - C++

03.04.2011, 17:17. Просмотров 1020. Ответов 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;
  }
}
Может где-то ошибка?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2011, 17:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Единицы (C++):

Дано натуральное число n. Отбросить в нем все цифры, стоящие правее самой правой единицы либо оставить число без изменений, если единицы в нем нет - C++
Дано натуральное число n. Отбросить в нем все цифры, стоящие правее самой правой единицы либо оставить число без изменений, если единицы в...

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

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

Единицы массы - C++
Ребята, помогите пожалуйста перевести программку с паскаля на С++: Единицы массы пронумерованы следующим образом: 1 — килограмм, ...

факториал с точностью до единицы - C++
Привет всем! Помогите исправить код,считает правильно все факториалы от 0 до 20,у остальных неверно. Посоветовали ввести ограничение на...

Шаблоны и единицы трансляции - C++
Всем привет. Единица трансляции - это *.cpp с включенными в него файлами, я так понимаю Тогда почему не работает такой вариант:...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ping_rulezzz
26 / 26 / 4
Регистрация: 18.02.2011
Сообщений: 51
03.04.2011, 22:00 #2
при каких значениях у вас валится программа? т.к. прокрутил цикл от 1 и до 5000 для переменной "a" - всё стабильно - не знаю на сколько корректные значения выводит, но нигде не крешится.
Единственное - добавьте return 0; в конец функции main()
0
Somebody
2789 / 1603 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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;
}
0
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, я не учёл исключений(((
А можешь мне порекомендовать какую нибудь книжку для динамического программирования, остальные я более или менее секу, вот на этих и на графах признаться я слабоват...
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2011, 16:50
Привет! Вот еще темы с ответами:

Распознать нули и единицы - C++
Помогите написать задачку, очень надо)) 00010001110 это условие 00010001010 00010001010 00010001110 и вот, что должно...

Степень минус единицы - C++
#include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;cstdlib&gt; #include &lt;cmath&gt; #include &lt;conio.h&gt; using namespace std; double...

Определяет единицы массы в кг - C++
Определяет единицы массы в кг, г, мг. Ниже приведены неметричес¬кие русские единицы массы: Берковец = 10 пудам = 163805 кг, пуд = 40...

Округление float до единицы - C++
Например есть число с плавающей точкой. Как его превратить в единицу без преобразования типа в int? Желательно без использования условных...


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

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

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