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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

Улучшение решения... - C++

07.04.2009, 17:13. Просмотров 1300. Ответов 2
Метки нет (Все метки)

Я тут решил задачку... Решение не оптимальное... Помогите улучшить... Вот задача:
Несчастливые номера
(Время: 1 сек. Память: 16 Мб)
Обычно автобусный билет с номером, состоящим из 6 цифр, считается счастливым, если сумма первых трех цифр его номера была равна сумме трех последних. Школьник Вася очень любил получать счастливые билеты, однако это случалось не так часто. Поэтому для себя он изменил определение счастливого билета.
Счастливым он считал тот номер, сумма некоторых цифр которого равнялась сумме оставшихся цифр. В его представлении билет с номером 561743 счастливый, так как 5+1+4+3=6+7.
Вася вырос, но по привычке в номерах различных документов пытается найти признаки счастливого номера Смайлик - улыбка. Для этого он расширил свое определение счастливого номера на N значные номера лицевых счетов и других документов, состоящих из цифр от 0 до K. Номер документа он называет счастливым, если сумма некоторых цифр этого номера равняется сумме оставшихся. Остальные номера для него несчастливые. К сожалению, несмотря на расширенное понимание “счастья”, несчастливых номеров остается еще много...
Вам предлагается определить количество несчастливых N-значных номеров, которые можно составить, используя цифры от 0 до K. В номерах допускается любое количество ведущих нулей.
Входные данные
Входной файл INPUT.TXT содержит описание вида номеров в виде двух чисел N и K, разделенных пробелом. (1 <= N <= 100, 1 <= K <= 9, N*K <= 300)
Выходные данные

В выходной файл OUTPUT.TXT выведите количество несчастливых номеров для заданных N и K.
Примеры
INPUT.TXT OUTPUT.TXT
1 7 7

4 3 164

11 9 50184219171



Вот мое решение
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
#include <cmath>
#include <cstdio>
#include <cstring>
int N, K, a[103], num[10], is[1010];
long long sum, tmp, fact[103];
void cnt( int n, int mi, int ss ){
     if (n == N){
           if (ss & 1)
           return;
     for (int i=0; i<ss+1; i++)
         is[i] = 0;
         is[0] = 1;
     int s = 0;
     for (int i=0; i<N; i++){
         if (is[ss/2])
         break;
     for (int j = s; j >= 0; j--)
        if (is[j])
           is[j+a[i]]=1;
        s += a[i];
    }
    if (is[ss/2])
    {
      tmp = 1;
      int rest = N;
      for (int i=0; i<K+1; i++)
          for (int j=0; j<num[i]; j++){
              tmp*=rest--;
              tmp/=j+1;
              }
      sum += tmp;
    }
    return;
  }
  for (int i = mi; i <= K; i++)
  {
    a[n] = i;
    num[i]++;
    cnt(n + 1, i, ss + i);
    num[i]--;
  }  
}
 
int main()
{
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  while (scanf("%d%d", &N, &K) == 2 && (N || K))
  {
    memset(num, 0, sizeof(num));
    sum = 0;
    fact[0] = 1;
    for (int i = 1; i <103; i++)
    fact[i]=i*fact[i-1];
    cnt(0,0,0);
    printf("%I64d\n", (long long)(pow(K + 1, N) + 0.5) - sum);
  }
  return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.04.2009, 17:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Улучшение решения... (C++):

Исправление ошибок и улучшение класса - C++
main()---------------------------------------------------- #include &lt;iostream&gt; #include &lt;ctime&gt; #include &lt;Windows.h&gt; #include...

Улучшение алгоритма записи строк - C++
В общем код полностью рабочий. В функции fill_start_file происходит запись в файл с условием, что строка не должна быть больше 80 символов....

Улучшение алгоритма подсчета строк, букв, слов - C++
Данный алгоритм, компилируется. Однако есть недочеты: 1. Не всегда верно считает буквы. Почему не очень понимаю. 2. Два спейса...

Улучшение алгоритма вычисления определителя матрицы, порядка n>3 - C++
Всем доброго времени суток, я достаточно долго искал шаблон кода для вычисления определителя квадратной матрицы, нашел на просторах рунета...

Метод решения - C++
С помощью какого метода лучше всего решить на C++ систему уравнений как на картинке ?

Решения уравнения - C++
1. (a+b)^2-(a^2+2ab)/a^2 b^2 +4ab^3 +b^4 при a=100 и b=0.001 2. (a+b)^3-(a^3)/3ab^2+b^3+3a^2 b при a=1000 и b=0,0001 ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
4elik
0 / 0 / 0
Регистрация: 03.02.2017
Сообщений: 3
03.02.2017, 17:21 #2
Здравствуйте, я новичок. Прошу прощения что подымаю такую древнюю тему, но вот и мне в моей шараге дали такое задание. Только вот я совсем не могу разобраться как вообще в функции
C++
1
cnt( int n, int mi, int ss)
может что-то выполняться, если мы передаем в нее нули
C++
1
cnt(0,0,0);
Может кто-нибудь растолкует, я уже и на бумажке пытался расписывать, все равно ничего не понятно.
0
MrGluck
Модератор
Эксперт CЭксперт С++
7239 / 4407 / 642
Регистрация: 29.11.2010
Сообщений: 11,927
03.02.2017, 17:27 #3
4elik, попробуйте использовать отладчик, или сделайте трассировку (cout на каждом непонятном шаге).
0, 0, 0 - начальные значения для алгоритма. Он использует и другие данные с которыми работает.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.02.2017, 17:27
Привет! Вот еще темы с ответами:

Оптимизация решения. - C++
всем привет. решил задачу - #include &lt;iostream&gt; #include &lt;fstream&gt; void print (const int *MAS, const char *, const int,...

есть решения??? - C++
Валя и Вера собрались варить варенье из А кг смородины. По рецепту на 2 кг ягод нужно 3 кг сахара. Валя сказала, что им потребуется С кг...

Решения по Дейтелам - C++
Ребят, такой вопрос, купил книгу Deitel H.M., Deitel P.J. / Дейтел Х.М., Дейтел П.Дж. - Как программировать на С++, очень много заданий,...

Решения матриц - C++
Уважаемые программисты прошу Вас помочь разобраться в решении 2-х задач. 1) Дана действительная матрица размера 6x9. Найти среднее...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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