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

Телефонные номера, которые набираются на кнопочном телефоне ходом коня - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.92
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
31.07.2014, 19:17     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #1
Динамическое программирование

Ход конем
(Время: 1 сек. Память: 16 Мб)
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Требуется написать программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

Входные данные

Входной файл INPUT.TXT содержит натуральное число N (N <= 100).

Выходные данные

В выходной файл OUTPUT.TXT выведите искомое количество телефонных номеров.


Помогите пожалуйста, сам решить не могу. Видел коды с других тем, но они пролетают по времени, заранее благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.07.2014, 19:17     Телефонные номера, которые набираются на кнопочном телефоне ходом коня
Посмотрите здесь:

Определить попарно номера окружностей, которые имеют хотя бы одну общую точку C++
C++ Обойти шахматную доску ходом коня
Определить сможет ли белый слон расположенный на поле (a,b),одним ходом пойти на поле (e,f),не попав при этом под удар чёрного коня нах.(c,d) C++
C++ Вывести на экран номера всех элементов,которые не делятся на 7.
Из Паскаля в С++ Вывести номера тех чисел в наборе, которые меньше своего левого соседа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
31.07.2014, 21:25     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #2
Neoks, вот так подойдет? По времени не проверял
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 <stdio.h>
 
#define n 3
 
int check(int x, int lvl)
{
    if (lvl == n-1 && (x == 4 || x == 6)) return 3;
        else return 6;
    switch (x)
    {
    case 1: return check(8, lvl+1)+check(6, lvl+1);
    case 2: return check(7, lvl+1)+check(9, lvl+1);
    case 3: return check(4, lvl+1)+check(8, lvl+1);
    case 4: return check(3, lvl+1)+check(9, lvl+1)+check(0, lvl+1);
    case 6: return check(1, lvl+1)+check(7, lvl+1)+check(0, lvl+1);
    case 7: return check(2, lvl+1)+check(6, lvl+1);
    case 8: return check(1, lvl+1)+check(3, lvl+1);
    case 9: return check(4, lvl+1)+check(2, lvl+1);
    case 0: return check(4, lvl+1)+check(6, lvl+1);
    }
}
 
int main(int argc, char *argv[])
{
    printf("%d\n", check(0, 1));
    return 0;
}
вызов функции будет слегка другой, надо будет вызвать функцию для всех необходимых первых номеров. Насчет правильности вроде норм
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
31.07.2014, 21:38     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #3
Хедин, 1) прога когда-нибудь в свитч заходит??? 2)Это не ДП.
Хедин
 Аватар для Хедин
73 / 68 / 36
Регистрация: 17.05.2014
Сообщений: 301
31.07.2014, 21:49     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #4
SlavaSSU, оу, мой косяк, сейчас поправлю

Добавлено через 5 минут
Neoks, вот так
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 <stdio.h>
 
#define n 4
 
int check(int x, int lvl)
{
    if (lvl == n-1)
        return (x == 4 || x == 6 ? 3 : 2);
    switch (x)
    {
    case 1: return check(8, lvl+1)+check(6, lvl+1);
    case 2: return check(7, lvl+1)+check(9, lvl+1);
    case 3: return check(4, lvl+1)+check(8, lvl+1);
    case 4: return check(3, lvl+1)+check(9, lvl+1)+check(0, lvl+1);
    case 6: return check(1, lvl+1)+check(7, lvl+1)+check(0, lvl+1);
    case 7: return check(2, lvl+1)+check(6, lvl+1);
    case 8: return check(1, lvl+1)+check(3, lvl+1);
    case 9: return check(4, lvl+1)+check(2, lvl+1);
    case 0: return check(4, lvl+1)+check(6, lvl+1);
    }
}
 
int main(int argc, char *argv[])
{
    printf("%d\n", check(0, 1));
    return 0;
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
31.07.2014, 22:12     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #5
C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
typedef long long li;
 
const int dxh[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dyh[] = {-1, 1, 2, 2, 1, -1, -2, -2};
 
bool in(int i, int j)
{
    return i <= 3 || j == 2;
}
 
li dp[111][5][5];
 
int main()
{
    int n;
    cin >> n;
 
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            dp[1][i][j] = 1;
    dp[1][3][2] = 0;
 
    for(int k = 1; k < n; k++)
    {
        for(int i = 1; i <= 4; i++)
        {
            for(int j = 1; j <= 3; j++)
            {
                for(int dir = 0; dir < 8; dir++)
                {
                    int ni = i + dxh[dir];
                    int nj = j + dyh[dir];
 
                    if(in(ni, nj))
                    {
                        dp[k + 1][ni][nj] += dp[k][i][j];
                    }
                }
            }
        }
    }
 
    li ans = 0;
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= 3; j++)
            ans += dp[n][i][j];
 
    cout << ans << endl;
    return 0;
}
Neoks
0 / 0 / 0
Регистрация: 31.07.2014
Сообщений: 8
01.08.2014, 18:49  [ТС]     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #6
Хедин, presentation error

Добавлено через 51 секунду
Вроде исправил, но все равно пролетает по времени

Добавлено через 43 секунды
http://********/index.asp?main=task&id_task=471
Trwsdf
Заблокирован
03.08.2014, 20:37     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #7
Neoks,SlavaSSU,Хедин -все ответы не верны.
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
03.08.2014, 20:58     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #8
Trwsdf, а примеров входных и выходных данных нет?

Добавлено через 12 минут
Trwsdf, у меня в переполнении косяк? или в идее?
Trwsdf
Заблокирован
03.08.2014, 21:13     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #9
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Trwsdf, а примеров входных и выходных данных нет?
Добавлено через 12 минут
Trwsdf, у меня в переполнении косяк? или в идее?
У вас вообще не правильный вывод.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
03.08.2014, 21:22     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #10
Вас чётко всех просили сделать ДП! А вы что отвечаете?
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
03.08.2014, 22:18     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #11
Trwsdf, ну так дай тест и правильный ответ
Trwsdf
Заблокирован
03.08.2014, 23:14     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #12
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Trwsdf, ну так дай тест и правильный ответ
lvl 1 2 3 5 ... 55
8 16 36 188 ... 177456951844650614784

Так должно быть
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
03.08.2014, 23:24     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #13
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
#include <stdio.h>
void sum(int *a,int *b,int *c,int *n)
{
    int i,t;
    for (i=t=0;i<*n+3;i++)
    {
        t+=a[i]+b[i];
        c[i]=t%10;
        t/=10;
    }
    *n+=3;
    while (!c[*n])
        --*n;
}
int d[20][200][200],s[200],n,i,j,l,m,p[20][5]={{2,4,6},{2,6,8},{2,7,9},{2,4,8},{3,0,3,9},{0},{3,0,1,7},{2,2,6},{2,1,3},{2,2,4}};
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    for (i=0;i<10;i++)
        d[i][0][0]=1;
    scanf("%d",&n);
    for (i=1;i<n;i++)
        for (j=0;j<10;j++)
            for (d[j][i][0]=l=0;l<p[j][0];l++)
            {
                m=100;
                sum(d[j][i],d[p[j][l+1]][i-1],d[j][i],&m);
            }
    for (m=100,i=1;i<10;i++)
        if (i!=8)
             
            sum(s,d[i][n-1],s,&m);
    for (i=m;i>=0;i--)
        printf("%d",s[i]);
    return 0;
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
04.08.2014, 00:08     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #14
Trwsdf, да, косяк был в функии in. но теперь у меня там все переполняется(

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
typedef long long li;
typedef unsigned long long uli;
 
const int dxh[] = {-2, -2, -1, 1, 2, 2, 1, -1};
const int dyh[] = {-1, 1, 2, 2, 1, -1, -2, -2};
 
bool in(int i, int j)
{
    return (i >= 1 && i <= 3 && j >= 1 && j <= 3) || (i == 4 && j == 2);
}
 
uli dp[111][5][5];
 
int main()
{
    int n;
    cin >> n;
 
    for(int i = 1; i <= 3; i++)
        for(int j = 1; j <= 3; j++)
            dp[1][i][j] = 1;
    dp[1][3][2] = 0;
 
    for(int k = 1; k < n; k++)
    {
        for(int i = 1; i <= 4; i++)
        {
            for(int j = 1; j <= 3; j++)
            {
                cerr << k << ' ' << i << ' ' << j << ' ' << dp[k][i][j] << endl;
                for(int dir = 0; dir < 8; dir++)
                {
                    int ni = i + dxh[dir];
                    int nj = j + dyh[dir];
 
                    if(in(ni, nj))
                    {
                        dp[k + 1][ni][nj] += dp[k][i][j];
                    }
                }
            }
        }
    }
 
    uli ans = 0;
    for(int i = 1; i <= 4; i++)
        for(int j = 1; j <= 3; j++)
            ans += dp[n][i][j];
 
    cout << ans << endl;
    return 0;
}
Trwsdf
Заблокирован
04.08.2014, 00:16     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #15
Вот так код, абсолютно нечитаемо и неподдерживаемо. Автор унес в могилу всю его поддержку. Однако видно, что кто то провел много времени составляя кубы ,оптимизируя, и тд. стараясь выпендриться. И конечно же, щас начнет доказывать, что все сделано на пару минут, но мне наплевать.
На C# главное проще и быстрей пишется, - что я за 10 минут и накидал собсно.

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
        int level = 1000;
            if (level <= 2) Console.Write((8 * level).ToString());
            else
            {
                System.Numerics.BigInteger[] num = new System.Numerics.BigInteger[9];
                System.Numerics.BigInteger[] index = new System.Numerics.BigInteger[9];
                System.Numerics.BigInteger buffer = new System.Numerics.BigInteger();
                System.Numerics.BigInteger sum = 0;
                for (int d = 1; d < 9; d = (d + 1 == 7) ? d + 2 : d + 1)
                {
                    if (d == 4 || d == 5) num[d] = 3; else num[d] = 2;
                    for (int k = 2; k < level; k++)
                    {
                        for (int di = 0; di < 9; di++)
                        {
                            index[di] = num[di];
                            num[di] = 0;
                        };
                        for (int i = 0; i < 9; i++)
                            if (index[i] != 0)
                                switch (i)
                                {
                                    case 0: buffer = 3 * index[i] / 2; num[4] += buffer; num[5] += buffer; break;
                                    case 1: num[5] += 3 * index[i] / 2; num[7] += index[i]; break;
                                    case 2: num[6] += index[i]; num[8] += index[i]; break;
                                    case 3: num[4] += 3 * index[i] / 2; num[7] += index[i]; break;
                                    case 4: buffer = 2 * index[i] / 3; num[3] += buffer; num[8] += buffer; num[0] += buffer; break;
                                    case 5: buffer = 2 * index[i] / 3; num[1] += buffer; num[6] += buffer; num[0] += buffer; break;
                                    case 6: num[2] += index[i]; num[5] += 3 * index[i] / 2; break;
                                    case 7: num[1] += index[i]; num[3] += index[i]; break;
                                    case 8: num[2] += index[i]; num[4] += 3 * index[i] / 2; break;
                                }
                    }
                    for (int di = 0; di < 9; di++)
                    {
                        sum += num[di];
                        num[di] = 0;
                    }
                }
                Console.Write(sum.ToString());
            }
            Console.ReadLine();
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,669
04.08.2014, 21:25     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #16
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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
/////////////////////////////////////////////////////////////////////////////////////////
//ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
//
//ХОД КОНЕМ
//(Время: 1 сек. Память: 16 Мб)
//Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, 
//которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается 
//телефон 340-49-27. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
//
//Требуется написать программу, определяющую количество телефонных номеров длины N, 
//набираемых ходом коня.
//
//ВХОДНЫЕ ДАННЫЕ
//
//Входной файл INPUT.TXT содержит натуральное число N (N <= 100).
//
//ВЫХОДНЫЕ ДАННЫЕ
//
//В выходной файл OUTPUT.TXT выведите искомое количество телефонных номеров.
/////////////////////////////////////////////////////////////////////////////////////////
#include <iomanip>
#include <iostream>
#include <limits>
#include <sstream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef unsigned long long  T_ull;
typedef std::string         T_str;
/////////////////////////////////////////////////////////////////////////////////////////
const   T_ull   MAX_ULL             =   std::numeric_limits<T_ull>::max();
const   int     TEL_NUM_LEN_MAX     =   103;
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T >
T_str   to_str( T   val )
{
    std::ostringstream  sout;
    sout    <<  val;
    return  sout.str();
}
/////////////////////////////////////////////////////////////////////////////////////////
class   T_big_int
{
    //-----------------------------------------------------------------------------------
    static  const   T_ull   FACTOR  =   T_ull(1e18);
    //-----------------------------------------------------------------------------------
    bool    is_overflow_;
    T_ull   head_;
    T_ull   tail_;
    //-----------------------------------------------------------------------------------
    friend  std::ostream    &   operator<<
        (
            std::ostream        &   os,
            T_big_int   const   &   big_int
        )
    {
        if( big_int.is_overflow_ )
        {
            os  <<  "overflow";
        }
        else
        {
            int     num_len     =   0;
            T_str   head_str    =   to_str( big_int.head_ );
            T_str   tail_str    =   to_str( big_int.tail_ );
 
            if( big_int.head_ > 0 )
            {
                num_len     +=  head_str.size();
                os          <<  head_str;
            }
 
            num_len     +=  tail_str.size();
 
            os          <<  tail_str
                        <<  std::endl
                        <<  "count_len = "
                        <<  num_len;
        }//else
 
        return  os;
    }
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_big_int( T_ull    ull = 0 )
        :
        is_overflow_    (),
        head_           (),
        tail_           ( ull )
    {
        normalize();
    }
    //-----------------------------------------------------------------------------------
    T_big_int   &   operator+=  ( T_big_int     const   &   i )
    {
        is_overflow_    =       is_overflow_
                            ||  i.is_overflow_;
 
        if( !is_overflow_ )
        {
            if( head_ > MAX_ULL - i.head_ )
            {
                is_overflow_    =   true;
            }
            else
            {
                head_   +=  i.head_;
                tail_   +=  i.tail_;
            }
 
            normalize();
        }//if
 
        return  *this;
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    void    normalize()
    {
        if( !is_overflow_ )
        {
            T_ull   head_delta  =  tail_ / FACTOR;
 
            if( head_delta > MAX_ULL - head_ )
            {
                is_overflow_    =   true;
            }
            else
            {
                head_   +=  head_delta;
                tail_   %=  FACTOR;
            }//else
        }//if
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
T_big_int     count_tel_numbers[10][TEL_NUM_LEN_MAX]    =   {0};
/////////////////////////////////////////////////////////////////////////////////////////
int     prev_digits_for[10][3]  =   {
                                        { 4,    6,  -1  },  //0
                                        { 6,    8,  -1  },  //1
                                        { 7,    9,  -1  },  //2
 
                                        { 4,    8,  -1  },  //3
                                        { 0,    3,  9   },  //4
                                        { -1,   -1, -1  },  //5
 
                                        { 0,    1,  7   },  //6
                                        { 2,    6,  -1  },  //7
                                        { 1,    3,  -1  },  //8
 
                                        { 2,    4,  -1  }   //9
                                    };
/////////////////////////////////////////////////////////////////////////////////////////
T_big_int   get_count_tel_numbers_val
    (
        int     first_digit,
        int     num_len_cur
    )
{
    T_big_int   res     =   0;
 
    for( int  j = 0; j < 3; ++j )
    {
        int     prev_digit  =   prev_digits_for[ first_digit ][ j ];
 
        if  (
                prev_digit >= 0
            )
        {
            res     +=  count_tel_numbers[ prev_digit ][ num_len_cur - 1 ];
        }//if
    }//for
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_big_int   count_tel_numbers_with_len( int     num_len )
{
    for( int  num_len_cur = 1; num_len_cur <= num_len; ++num_len_cur )
    {
        for( int  first_digit = 0; first_digit < 10; ++first_digit )
        {
            if( num_len_cur == 1 )
            {
                count_tel_numbers[first_digit][num_len_cur] = 1;
            }
            else
            {
                count_tel_numbers[first_digit][num_len_cur]     =   get_count_tel_numbers_val
                                                                        (
                                                                            first_digit,
                                                                            num_len_cur
                                                                        );
            }//else
        }//for
    }//for
 
    T_big_int   res     =   0;
 
    for( int  first_digit = 0; first_digit < 10; ++first_digit )
    {
        if  (
                    first_digit     !=  0
                &&  first_digit     !=  8
            )
        {
            res     +=  count_tel_numbers[ first_digit ][ num_len ];
        }//if
    }//for
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
template< typename  T >
void    print_prompt_and_input_val_in_segment
    (
        T_str   const   &   prompt,
        T               &   val,
        T                   left_bound,
        T                   right_bound
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while   (
                    val             <   left_bound
                ||  right_bound     <   val
            );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    for(;;)
    {
        int     num_len     =   0;
        T_str   prompt      =       T_str( "Phone number length (" )
                                +   to_str( 1 )
                                +   ".."
                                +   to_str( TEL_NUM_LEN_MAX )
                                +   "): ";
 
        print_prompt_and_input_val_in_segment
            (
                prompt,
                num_len,
                1,
                TEL_NUM_LEN_MAX
            );
 
        std::cout   <<  count_tel_numbers_with_len( num_len )
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.08.2014, 01:05     Телефонные номера, которые набираются на кнопочном телефоне ходом коня
Еще ссылки по теме:

Дана матрица A(7,3). Определить количество строк, которые содержат нулевые елементы, их номера C++
Дана матрица A(7,3). Определить количество строк, которые содержат нулевые елементы, их номера C++
C++ Вывести порядковые номера тех людей, которые родились ранее 1955 года, посчитать их количество

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

Или воспользуйтесь поиском по форуму:
Trwsdf
Заблокирован
05.08.2014, 01:05     Телефонные номера, которые набираются на кнопочном телефоне ходом коня #17
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int level = 20;
    unsigned long long sum = 0;
    char init[][3] = { { 4, 5, -1 }, { 5, 7, -1 }, { 6, 8, -1 }, { 4, 7, -1 }, { 3, 8, 0 }, { 1, 6, 0 }, { 2, 5, -1 }, { 1, 3, -1 }, { 2, 4, -1 } };
    unsigned long long data[2][9] = {{0, 0, 0, 0, 0, 0, 0, 0, 0}};
    for (int d = 1; d < 9; d = (d + 1 == 7) ? d + 2 : d + 1) {
        data[0][d] = 1;
        for (int k = 1; k < level; k++) {
            for (int di = 0; di < 9; di++) {
                data[1][di] = data[0][di];
                data[0][di] = 0;
            };
            for (int i = 0; i < 9; i++)
                if (data[1][i] != 0)
                    for (int ci = 0; ci < ((i == 4 || i == 5) ? 3 : 2); ci++) data[0][init[i][ci]] += data[1][i];
        }
        for (int di = 0; di < 9; di++) {
            sum += data[0][di];
            data[0][di] = 0;
        }
    };
    printf("%i", sum);
Yandex
Объявления
05.08.2014, 01:05     Телефонные номера, которые набираются на кнопочном телефоне ходом коня
Ответ Создать тему
Опции темы

Текущее время: 23:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru