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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Составить алгоритм к программе http://www.cyberforum.ru/cpp-beginners/thread29077.html
Нужно составить алгоритм, помогите пожалуйста :help: Эта программа: Определяет первый положительный максимальный элемент и его позицию в массиве, а также количество положительных элементов. #include<iostream.h> int main(){ int m; int n,Max,v,k; Max=0;
C++ Плавающие числа (Время: 1 сек. Память: 16 Мб ) Дано N целых чисел. Каждое из них можно один раз изменить не более чем на целую величину L как в сторону увеличения, так и в сторону уменьшения или оставить без изменения. Если после такой операции некоторые из чисел оказываются равными, то они засчитываются за одно. С данными числами произвели указанную операцию таким образом, что осталось минимально возможное... http://www.cyberforum.ru/cpp-beginners/thread29074.html
Определить расстояние от данной точки до ломаной C++
Есть задача. Вот ее краткий пересказ. На плосткости дана точка с координатами x и у. Дано n. На плоскости дано n точек, попарно соединенных прямыми, чтобы получилась замкнутая ломанная (первая со второй, вторая с третьей ... n-я с первой). Определить расстояние от данной точки до ломанной. Есть решение, но понять, что в нем не так, не получается уже третий день. #include "stdafx.h"...
C++ Составить программу для нахожления точки пересечения этих функций
Кто нить кто понимает с++ помогите с задачкой :) Дана парабола y=ax2+bx+с и прямая y=kx+m. Составить программу для нахожления точки пересечения этих функций, если тковая существует. В случае если пересения нет, выдать специальное сообщение. Зарание спасибо :)
C++ Строки немогу найти решения или нехватает литературы чтоб самому разобраться http://www.cyberforum.ru/cpp-beginners/thread29059.html
подскажите пожалуйста как решить эти задачи методом для начинающего или где можно взять литературу по строкам пожалуйста заранее благодарен 1.Дана строка. Заменить в строке все большые буквы на маленькие и наоборот. 2.Написать функцию, которая получает строку и возвращает длину строки. Без использования функции strlen() 3.Дана строка. Удалить из строки заданный символ. Результат...
C++ Поиск экстремумов функции Вообще завал(( Была задана такая задача: Найти экстремумы функции y=2*sin(3*x) С чего вообще начать решать эту задачу? Есть ли какие-нибудь специальные функции(и если есть какие нужны библиотеки) чтобы реализовать алгоритм на Borland C++ ? подробнее

Показать сообщение отдельно
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254

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

07.04.2009, 17:13. Просмотров 1280. Ответов 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru