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

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

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

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

28.04.2012, 21:58. Просмотров 5215. Ответов 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;
}
зацикливает,объясните что не так
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2012, 21:58
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Подсчитать общее количество «счастливых» билетов (C++):

Подсчитать количество "счастливых" шестизначных билетов в рулоне и вывести их номера на экран - C++
Напишите программу, которая подсчитывает количество &quot;счастливых&quot; билетов в рулоне и выводит их номера на экран. Номер билета - шестизначное...

Определить количество счастливых билетов - C++
Имеется часть катушки с автобусными билетами. Номер билета 6-ти значный. Составить программу. определяющую кол-во счастливых билетов! Я...

Подсчитать количество "счастливых" шестизначных автобусных билетов(сумма первых трех цифр равна сумме трех последних цифр) - C++
Подсчитать количество &quot;счастливых&quot; шестизначных автобусных билетов, т.е таких, в номерах которых сумма трех первых цифр равна сумме трех...

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

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

Найти количество счастливых билетов с 6-значными номерами - C++
Найти количество счастливых билетов в серии ABC, то есть с 6 - значными номерами вида ABCXXX, счастливым билет считается с номером ABCDEF,...

16
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 240
28.04.2012, 22:28 #2
Оно не зацикливает, а считает. Закомментируйте вывод в цикле - и не будет бешеной вереницы номеров:
C++
1
//cout<<i<<"\t";
0
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
28.04.2012, 22:30  [ТС] #3
а количество как?
0
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 240
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;
}
0
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
28.04.2012, 22:47  [ТС] #5
пишет ответ неправильный,должен быть 55251,а у нее 50412
0
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 240
28.04.2012, 22:52 #6
55251 счастливых билетов - это если с 1 считать.
В данной программе отсчет идет от 100000 - в ней не учитываются номер, например, 001001.
0
enota
0 / 0 / 0
Регистрация: 03.03.2012
Сообщений: 36
28.04.2012, 23:54  [ТС] #7
и как сделать?изменить начало отсчета только?

Добавлено через 35 минут
как ж все же сделать?
0
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;
}
0
DU
1483 / 1129 / 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;
}
0
diagon
Higher
1930 / 1196 / 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;
}
0
amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 240
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 минут
как ж все же сделать?
Ну да - всё гениальное просто.
0
LK
29.04.2012, 17:52
  #12
 Комментарий модератора 
enota, Правила
п.3.4. Запрещено размещать тему в нескольких разделах одновременно (кросспостинг), а также дублировать тему в одном разделе.
Если у вас есть дополнение к уже созданной теме, найдите эту свою тему и сделайте это дополнение.
Ваша аналогичная тема:
Счастливый билет (удалена)
Устное предупреждение.
0
From_Tula
40 / 40 / 2
Регистрация: 22.05.2009
Сообщений: 483
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];
}
0
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;
А для С# как это реализуется?
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
27.12.2012, 23:43 #15
Цитата Сообщение от The_Japanese Посмотреть сообщение
А для С# как это реализуется?
В 4 фреймворке уже реализовано(System.Numerics.BigInteger)
1
27.12.2012, 23:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.12.2012, 23:43
Привет! Вот еще темы с ответами:

Составить программу, определяющую количество счастливых билетов на катушке - C++
6.3.2. Помогите, пожалуйста, решить задачу в С++ с помощью функций. Имеется часть катушки с автобусными билетами. Номер билета...

Найти количество счастливых билетов учитывая скорость выполнения программы - C++
Найти количество счастливых билетов учитывая скорость выполнения программы,счастливый билет имеет вид a+b+c=d+e+f.

Середи всех шестизначных чисел проверить и подсчитать колличество "счастливых" билетов - C++
1.Середи всех шестизначных чисел проверить и подсчитать колличество &quot;счастливых&quot; билетов. 2.Цех по ремонту бітовой техники имеет...

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


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

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

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