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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.71
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
#1

Подсчитать общее количество «счастливых» билетов - C++

28.04.2012, 21:58. Просмотров 4673. Ответов 16
Метки нет (Все метки)

Подсчитать общее количество «счастливых» билетов. Билет имеет шестизначный номер и является счастливым, если сумма первых трех цифр равна сумме последних цифр. Ответ вывести на экран. ПРМЕЧАНИЕ: Билет с номером 000000 не существует.
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
#include <iostream.h>
 
int main(void)
{
   int i, a, b, c, d, e, f, x, y, n = 0;
 
   for (i=100000; i<=999999; i++)
   {
      a=i/100000;
      b=i/10000-a*10;
      c=i/1000-a*100-b*10;
      d=i/100-a*1000-b*100-c*10;
      e=i/10-a*10000-b*1000-c*100-d*10;
      f=i-a*100000-b*10000-c*1000-d*100-e*10;
 
      x=a+b+c;
      y=d+e+f;
 
      if (x==y)
      {
         cout<<i<<"\t";
         ++n;
      }
   }
   cout << endl << "Count = " << n << endl;
   return 0;
}
зацикливает,объясните что не так
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2012, 21:58     Подсчитать общее количество «счастливых» билетов
Посмотрите здесь:

Середи всех шестизначных чисел проверить и подсчитать колличество "счастливых" билетов C++
C++ Определить количество счастливых билетов
C++ Подсчитать количество "счастливых" шестизначных автобусных билетов(сумма первых трех цифр равна сумме трех последних цифр)
C++ Найти количество всевозможных шестизначных счастливых билетов
C++ Составить программу, определяющую количество счастливых билетов на катушке
C++ Программа, которая подсчитывает количество "счастливых" билетов в рулоне и выводит их номера на экран
C++ Подсчитать количество "счастливых" шестизначных билетов в рулоне и вывести их номера на экран
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 238
28.04.2012, 22:28     Подсчитать общее количество «счастливых» билетов #2
Оно не зацикливает, а считает. Закомментируйте вывод в цикле - и не будет бешеной вереницы номеров:
C++
1
//cout<<i<<"\t";
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
28.04.2012, 22:30  [ТС]     Подсчитать общее количество «счастливых» билетов #3
а количество как?
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 238
28.04.2012, 22:41     Подсчитать общее количество «счастливых» билетов #4
А что с количеством? - оно выводится в самом конце, все нормально.
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
#include <iostream.h>
 
int main(void)
{
   int i, a, b, c, d, e, f, x, y, n = 0;
 
   for (i=100000; i<=999999; i++)
   {
      a=i/100000;
      b=i/10000-a*10;
      c=i/1000-a*100-b*10;
      d=i/100-a*1000-b*100-c*10;
      e=i/10-a*10000-b*1000-c*100-d*10;
      f=i-a*100000-b*10000-c*1000-d*100-e*10;
 
      x=a+b+c;
      y=d+e+f;
 
      if (x==y)
      {
         //cout<<i<<"\t";  //комментируем, ибо незачем видеть промежуточные количества
         ++n;
      }
   }
   cout << endl << "Count = " << n << endl;
   return 0;
}
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
28.04.2012, 22:47  [ТС]     Подсчитать общее количество «счастливых» билетов #5
пишет ответ неправильный,должен быть 55251,а у нее 50412
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 238
28.04.2012, 22:52     Подсчитать общее количество «счастливых» билетов #6
55251 счастливых билетов - это если с 1 считать.
В данной программе отсчет идет от 100000 - в ней не учитываются номер, например, 001001.
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
28.04.2012, 23:54  [ТС]     Подсчитать общее количество «счастливых» билетов #7
и как сделать?изменить начало отсчета только?

Добавлено через 35 минут
как ж все же сделать?
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
29.04.2012, 00:10     Подсчитать общее количество «счастливых» билетов #8
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>
using namespace std;
 
int main(void)
{
    int k = 0;
    for (int i = 1; i <= 999999; ++i)
    {
        int n = i, a = 0, b = 0, q = 0;      
        while(n)
        {
            ++q;
            if (q <= 3)
                a += n % 10;
            else 
                b += n % 10;
            n /= 10;
        }
 
        if (a == b)
            ++k;
    }
 
    cout << "Count = " << k << endl;
    return 0;
}
DU
1480 / 1056 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
29.04.2012, 01:21     Подсчитать общее количество «счастливых» билетов #9
Вот чуть более хитрый алгоритм. В нем в 1000 раз меньше итераций (впрочем, этого можно и в предложенных алгоритмах достигнуть). Но такой алгоритм вроде по проще будет:

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
#include <iostream>
 
int main()
{
  // Для начала нужно посчитать количество одинаковых сумм для первой 
  // половины шестизнаяного числа. Т.е. от 0 до 999;
  // Максимально возможная сумма из трех цифр
  const unsigned maxSumm = 9 + 9 + 9;
 
  // Т.е. всего возможно 27 различных сумм плюс нулевая сумма, которую потом
  // не будем учитывать.
  // Итого нужен массив на 27 + 1 ячеек.
  unsigned summs[maxSumm + 1] = {0};
 
  // Цикл крутится по рязрядам. Сумма рязрядов i + j + k будет иднексом для ячейки.
  // Мы будет обращаться к этой ячейке и увеличивать ее на еденицу. Т.о. мы
  // опредим частоту определенной суммы (индекс ячейки равен сумме разрядов, значение
  // в ячейке - как часто она встречалась).
  for (int i = 0; i < 10; ++i)
  {
    for (int j = 0; j < 10; ++j)
    {
      for (int k = 0; k < 10; ++k)
      {
        ++summs[i + j + k];
      }
    }
  }
 
  // Вот теперь в массиве у нас есть частота различных сумм. Остается сложить квадраты
  // этих частот. Первую ячейку (с индексом 0) мы пропускаем, потому что в ней сумма
  // трех нулей, а нулевого билета не бывает.
  unsigned happyTickets = 0;
  for (int i = 1; i < maxSumm; ++i)
  {
    happyTickets += summs[i] * summs[i];
  }
 
  std::cout << "Happy tickets count = " << happyTickets << std::endl;
 
  return 0;
}
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
29.04.2012, 06:44     Подсчитать общее количество «счастливых» билетов #10
Для Nзначных билетов(вводим N, получаем количество):
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 #include <iostream>
#include <vector>
#include <cmath>
#include <sstream>
#include <string>
#include <iomanip>
#include <cstdlib>
 
class BigInteger
{
protected:
 
    std::vector<int> value;
    static const int base = 1e9;
    static const int count_of_digits = 9;
    
public:
 
    BigInteger();   
    BigInteger( const std::string& );
    BigInteger( long long );
    
    BigInteger& operator = ( const BigInteger& );
    BigInteger& operator += ( const BigInteger& );
    BigInteger& operator *= ( const BigInteger& );
    
    friend BigInteger operator + ( const BigInteger&, const BigInteger& );
    friend BigInteger operator * ( const BigInteger&, const BigInteger& );
    
    friend std::istream& operator >> ( std::istream&, BigInteger& );
    friend std::ostream& operator << ( std::ostream&, const BigInteger& );
};
 
 
typedef BigInteger bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
 
int main()
{
    int n;
    std::cin >> n;
    
    if ( n % 2 != 0 || n < 2 )
    {
        std::cerr << "Incorrect input!\n";
        return EXIT_FAILURE;
    }
    
    n /= 2;
    
    matrix_t dinamic(n + 1, std::vector< bigInt > (n * 9 + 1) );
    
    /* dinamic[i][j] - количество i-значных билетов с суммой цифр, равной j */
    
    /* количество однозначных билетов с суммой цифр i (0 <= i <= 9) равно 1 */
    for (int i = 0; i <= 9 ; ++i)
        dinamic.at(1).at(i) = 1; 
        
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j <= i * 9 ; ++j)
        {
            for ( int k = 0 ; k <= std::min( j, 9 ) ; ++k)
            {
                dinamic.at(i).at(j) += dinamic.at(i - 1).at(j - k);
            }
        }
    }
    
    bigInt answer = 0;
    
    for (int i = 0 ; i <= n * 9  ; ++i)
        answer += dinamic.at(n).at(i) * dinamic.at(n).at(i);
        
    std::cout << answer;
}
 
BigInteger::BigInteger( const std::string& str )
{
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
}
 
BigInteger::BigInteger()
{
    value.push_back(0);
}
 
BigInteger::BigInteger( long long x )
{
    std::ostringstream ost;
    ost << x;
    std::string str = ost.str();
    
    for (int i = str.length() ; i > 0 ; i -= count_of_digits)
    {
        if ( i < count_of_digits )
        {
            value.push_back( atoi( str.substr(0, i).c_str() ) );
        }
        else
        {
            value.push_back( atoi( str.substr(i - count_of_digits, count_of_digits).c_str() ) );
        }
    }
    
}
 
BigInteger& BigInteger::operator += ( const BigInteger& b )
{
    for ( int temp = 0, i = 0; i < (int) std::max( this->value.size(), b.value.size() ) || temp != 0 ; ++i)
    {
        if ( i == (int) value.size() )
            value.push_back( 0 );
        
        value[i] += temp + ( i < (int) b.value.size() ? b.value[i] : 0 );
        temp = value[i] >= base;
        
        if ( temp != 0 )
            value[i] -= base;
    }
    
    return *this;
}
 
BigInteger operator + ( const BigInteger& a, const BigInteger& b )
{
    BigInteger c = a;
    c += b;
    return c;
}
 
std::istream& operator >> ( std::istream& stream, BigInteger& big )
{
    std::string str;
    std::cin >> str;
    big = BigInteger(str);
    
    return stream;  
}
 
std::ostream& operator << ( std::ostream& stream, const BigInteger& big )
{
    if ( big.value.empty() )
        stream << 0;
    else
        stream << big.value.back();
        
    for (int i = (int) big.value.size() - 2; i >= 0; --i)
    {
        stream << std::setfill('0') << std::setw(BigInteger::count_of_digits) << big.value[i];
    }
    
    return stream;
}
 
BigInteger& BigInteger::operator = ( const BigInteger& big )
{
    this->value = big.value;
    
    return *this;
}
 
BigInteger operator * ( const BigInteger& a, const BigInteger& b )
{
    BigInteger c;
    c.value.resize( a.value.size() + b.value.size() );
    
    for (int i = 0; i < (int) a.value.size(); ++i)
    {
        for (int j = 0, carry = 0 ; j < (int) b.value.size() || carry != 0 ; ++j)
        {
            long long cur = c.value[i + j] + a.value[i] * 1ll * ( j < (int) b.value.size() ? b.value[j] : 0 ) + carry;
            
            c.value[i + j] = int( cur % BigInteger::base );
            
            carry = int ( cur / BigInteger::base );         
        }   
    }
    
    while ( c.value.size() > 1 && c.value.back() == 0 )
    {
        c.value.pop_back();
    }
    
    return c;
}
 
BigInteger& BigInteger::operator *= ( const BigInteger& big )
{
    BigInteger a = *this;
    *this = a * big;
    return *this;
}
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 238
29.04.2012, 10:09     Подсчитать общее количество «счастливых» билетов #11
Еще вариант:
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
#include <iostream>
using namespace std;
 
int bilet()
{
    int sum = 0;
    int i, j, k;
    char bilet[6];
    for (i = 1; i <= 999999; i++)
    {
        for (k = i, j = 0; j < 6; j++, k /= 10)
            bilet[j] = k % 10;
        if (bilet[0]+bilet[1]+bilet[2] == bilet[3]+bilet[4]+bilet[5])
            ++sum;
    }
    return sum;
}
 
int main()
{
    int k = bilet();
    cout << "The number of bilets: " << k << endl;
    return 0;
}
Добавлено через 37 секунд
Цитата Сообщение от enota Посмотреть сообщение
и как сделать?изменить начало отсчета только?
Добавлено через 35 минут
как ж все же сделать?
Ну да - всё гениальное просто.
LK
29.04.2012, 17:52
  #12
 Комментарий модератора 
enota, Правила
п.3.4. Запрещено размещать тему в нескольких разделах одновременно (кросспостинг), а также дублировать тему в одном разделе.
Если у вас есть дополнение к уже созданной теме, найдите эту свою тему и сделайте это дополнение.
Ваша аналогичная тема:
Счастливый билет (удалена)
Устное предупреждение.
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 481
14.06.2012, 18:11     Подсчитать общее количество «счастливых» билетов #13
Почему этот алгоритм находит 55250 решений, никак не могу понять...
Где 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
 
int main()
{
  // Для начала нужно посчитать количество одинаковых сумм для первой 
  // половины шестизнаяного числа. Т.е. от 0 до 999;
  // Максимально возможная сумма из трех цифр
  const unsigned maxSumm = 9 + 9 + 9;
 
  // Т.е. всего возможно 27 различных сумм плюс нулевая сумма, которую потом
  // не будем учитывать.
  // Итого нужен массив на 27 + 1 ячеек.
  unsigned summs[maxSumm + 1] = {0};
 
  // Цикл крутится по рязрядам. Сумма рязрядов i + j + k будет иднексом для ячейки.
  // Мы будет обращаться к этой ячейке и увеличивать ее на еденицу. Т.о. мы
  // опредим частоту определенной суммы (индекс ячейки равен сумме разрядов, значение
  // в ячейке - как часто она встречалась).
  for (int i = 0; i < 10; ++i)
  {
    for (int j = 0; j < 10; ++j)
    {
      for (int k = 0; k < 10; ++k)
      {
        ++summs[i + j + k];
      }
    }
  }
 
  // Вот теперь в массиве у нас есть частота различных сумм. Остается сложить квадраты
  // этих частот. Первую ячейку (с индексом 0) мы пропускаем, потому что в ней сумма
  // трех нулей, а нулевого билета не бывает.
  unsigned happyTickets = 0;
  for (int i = 1; i < maxSumm; ++i)
  {
    happyTickets += summs[i] * summs[i];
  }
 
  std::cout << "Happy tickets count = " << happyTickets << std::endl;
 
  return 0;
}
Ошибка:
C++
1
2
3
for (int i = 1; i [B][COLOR="Red"]<=[/COLOR][/B] maxSumm; ++i) {
   happyTickets += summs[i] * summs[i];
}
The_Japanese
0 / 0 / 0
Регистрация: 19.03.2011
Сообщений: 9
27.12.2012, 23:42     Подсчитать общее количество «счастливых» билетов #14
Цитата Сообщение от diagon Посмотреть сообщение
Для Nзначных билетов(вводим N, получаем количество):
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
protected:
 
    std::vector<int> value;
    static const int base = 1e9;
    static const int count_of_digits = 9;
    
public:
 
    BigInteger();   
    BigInteger( const std::string& );
    BigInteger( long long );
    
    BigInteger& operator = ( const BigInteger& );
    BigInteger& operator += ( const BigInteger& );
    BigInteger& operator *= ( const BigInteger& );
    
    friend BigInteger operator + ( const BigInteger&, const BigInteger& );
    friend BigInteger operator * ( const BigInteger&, const BigInteger& );
    
    friend std::istream& operator >> ( std::istream&, BigInteger& );
    friend std::ostream& operator << ( std::ostream&, const BigInteger& );
};
 
 
typedef BigInteger bigInt;
typedef std::vector< std::vector< bigInt > > matrix_t;
А для С# как это реализуется?
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.12.2012, 23:43     Подсчитать общее количество «счастливых» билетов #15
Цитата Сообщение от The_Japanese Посмотреть сообщение
А для С# как это реализуется?
В 4 фреймворке уже реализовано(System.Numerics.BigInteger)
The_Japanese
0 / 0 / 0
Регистрация: 19.03.2011
Сообщений: 9
28.12.2012, 00:19     Подсчитать общее количество «счастливых» билетов #16
Цитата Сообщение от diagon Посмотреть сообщение
В 4 фреймворке уже реализовано(System.Numerics.BigInteger)
У меня фреймворк 4, но System.Numerics.BigInteger нет...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2012, 00:36     Подсчитать общее количество «счастливых» билетов
Еще ссылки по теме:

C++ Месса. Подсчитать общее количество рукопожатий.
Найти количество счастливых билетов с 6-значными номерами C++
Найти количество счастливых билетов учитывая скорость выполнения программы C++
Найти количество счастливых билетов с шестизначными номерами C++
C++ Вывести на экран количество и номера (в несколько столбиков) всех счастливых билетов в заданном диапазоне

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1924 / 1190 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
28.12.2012, 00:36     Подсчитать общее количество «счастливых» билетов #17
Цитата Сообщение от The_Japanese Посмотреть сообщение
У меня фреймворк 4, но System.Numerics.BigInteger нет...
Он в отдельной дллке лежит. Вам нужно добавить ссылку на эту дллку. Это делается вроде через Project->Add Reference->вкладка с .NET->System.Numerics. Писал по памяти, могу ошибаться.

Добавлено через 13 минут
В 12 студии чуть по другому, нужно сделать правый клик по проекту, выбрать Add Reference(добавить ссылку), и уже там искать System.Numerics.
Переведенный за две минуты вариант для шарпа без проверок на входные данные и прочих наворотов:
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
using System;
using System.Numerics;
 
class Program
{
    static void Main()
    {
        Console.Write("Enter n: ");
        int n = int.Parse(Console.ReadLine()) / 2;
 
        var dinamic = new BigInteger[n + 1, n * 9 + 1];
 
        for (int i = 0; i <= 9; ++i)
            dinamic[1, i] = 1;
 
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 0; j <= i * 9; ++j)
            {
                for (int k = 0; k <= Math.Min(j, 9); ++k)
                {
                    dinamic[i, j] += dinamic[i - 1, j - k];
                }
            }
        }
 
        BigInteger answer = 0;
 
        for (int i = 0; i <= n * 9; ++i)
            answer += dinamic[n, i] * dinamic[n, i];
 
        Console.WriteLine(answer);
    }
}
Yandex
Объявления
28.12.2012, 00:36     Подсчитать общее количество «счастливых» билетов
Ответ Создать тему
Опции темы

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