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

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

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

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

31.07.2014, 19:17. Просмотров 1811. Ответов 16
Метки нет (Все метки)

Динамическое программирование

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

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

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

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

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

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


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

Вывести на печать телефонные номера, что начинаются на 22, которые имеют наибольший долг - C++
задание: список абонентов телефонной сети:почтовый номер , ФИО , адрес , номер телефона (ввести по шаблону 00-000-000) долг по оплате ....

Обойти шахматную доску ходом коня - C++
Обязательные условия: 1. Рекурсивный алгоритм. 2. Размер доски вводит пользователь. 3. Использовать динамический массив. #include...

Покрытие шахматной доски ходом коня - C++
4. Покрытие шахматной доски ходом коня.

Телефонные номера - C++
Телефонные номера Ограничение времени 1 секунда Ограничение памяти 64Mb Ввод стандартный ввод или input.txt Вывод стандартный...

Определить сможет ли белый слон расположенный на поле (a,b),одним ходом пойти на поле (e,f),не попав при этом под удар чёрного коня нах.(c,d) - C++
ребята помогите пожалуйста!я в с++ вообще не бум-бум! у меня 2-е задачи с шахматами!а я даже играть не умею в них!помогите пожалуйста!я...

Номера, набираемые ходом коня - Pascal ABC
Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом...

16
Хедин
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;
}
вызов функции будет слегка другой, надо будет вызвать функцию для всех необходимых первых номеров. Насчет правильности вроде норм
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
31.07.2014, 21:38 #3
Хедин, 1) прога когда-нибудь в свитч заходит??? 2)Это не ДП.
0
Хедин
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;
}
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
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;
}
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
0
Trwsdf
Заблокирован
03.08.2014, 20:37 #7
Neoks,SlavaSSU,Хедин -все ответы не верны.
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
03.08.2014, 20:58 #8
Trwsdf, а примеров входных и выходных данных нет?

Добавлено через 12 минут
Trwsdf, у меня в переполнении косяк? или в идее?
0
Trwsdf
Заблокирован
03.08.2014, 21:13 #9
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Trwsdf, а примеров входных и выходных данных нет?
Добавлено через 12 минут
Trwsdf, у меня в переполнении косяк? или в идее?
У вас вообще не правильный вывод.
0
Kuzia domovenok
1892 / 1747 / 119
Регистрация: 25.03.2012
Сообщений: 5,936
Записей в блоге: 1
03.08.2014, 21:22 #10
Вас чётко всех просили сделать ДП! А вы что отвечаете?
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
03.08.2014, 22:18 #11
Trwsdf, ну так дай тест и правильный ответ
0
Trwsdf
Заблокирован
03.08.2014, 23:14 #12
Цитата Сообщение от SlavaSSU Посмотреть сообщение
Trwsdf, ну так дай тест и правильный ответ
lvl 1 2 3 5 ... 55
8 16 36 188 ... 177456951844650614784

Так должно быть
0
dr.curse
389 / 345 / 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;
}
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
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;
}
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();
0
04.08.2014, 00:16
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2014, 00:16
Привет! Вот еще темы с ответами:

Найти способ обойти все поля ходом шахматного коня - PascalABC.NET
Доброго времени суток! Задача: Для шахматной доски размера k*k (k&gt;=5) найти способ обойти все поля ходом шахматного коня. Не...

Если возможно, с поля (k, l) одним ходом коня попасть на поле (m, n) - C (СИ)
Поле шахматной доски определяется парой натуральных чисел, первое из которых задает номер вертикали, а второе - номер горизонтали. Даны...

Теория графов (ходом коня пройти по всем ячейкам шахматной доски) - Delphi
можно ли ходом коня пройти по всем ячейкам шахматной доски (8х8)? если можно напишите алгоритм программы.

Определить, возможно ли попасть из одной клетки в другую одним ходом шахматного коня - Turbo Pascal
Заданы две клетки шахматной доски. Требуется определить, возможно ли попасть из одной клетки в другую одним ходом шахматного коня, а если...


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

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

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