Форум программистов, компьютерный форум, киберфорум
C++
Форум программистов и сисадминов Киберфорум > Форум программистов > C++
Войти
Регистрация
Восстановить пароль
Правила Карта Блоги Социальные группы Поиск Сообщения за день  
Другие темы раздела
C++ Возможно переписать программу? https://www.cyberforum.ru/ cpp/ thread153534.html
Есть программа Upgrade UA.exe хочу запустить ее на windows mobile 6. Возможно ли ее переписать. 		scanf C++
Пусть нужно читать из текста слова, пропуская все символы, кроме a-z и A-Z. То есть из текста Hello, world! ololo O_o получить только Hello world ololo O o Меня интересует, можно ли это...
C++ Вернуть stdin в консоль
Допустим я перенаправил поток stdin/stdout в файл с помощью функции freopen. Как заставить его снова работать с консолью? Добавлено через 9 минут Нашел. #include <cstdlib> #include <stdio.h>... 		C++ Прошу помочь.Подключение dll на неуправляемом С/С++ Возникла проблема.Есть рабочая dll, необходимо подключить к CLR приложению. Подключение происходит нормально. Все функции работают нормально кроме одной(хотя dll проверял все работает в обычных... https://www.cyberforum.ru/ cpp/ thread152917.html
C++ Не сразу закрывающаяся программа https://www.cyberforum.ru/ cpp/ thread152799.html
Есть команды в терминале.. вроде telnet или sql, эти программы запускаешь и они остаются открытыми пока не дашь команду, например, quit. Во время работы программы она показывает знак приглашения... 		C++ Парсер на С
вопшем есть файл с текстом..... в етом файле есть какие даные(мусор)...и есть дни: Понедельник,Вторник,среда......с етого файла нада вывести ети дни в порядке нахождениэ... ето походу несложная...
C++ Кто нибудь подскажет где можно найти исходник С/C++ алгоритм сжатия
Народ помогите, у меня времени нет чтобы самому разрабатывать алгоритм сжатия очень нужен алгоритм ещё лучше если на Asm (MMX, SSE2-3, SIMD) чтобы без потери данных а с восстановлением. Может какие... 		C++ ANSI или UNICODE Всем привет!!! У меня возникла такая ситуация что использовать в WinApi программирование ANSI или UNICODE, где-то читал, что UNICODE работает быстрее, чем ANSI, так как при использование ANSI он ... https://www.cyberforum.ru/ cpp/ thread151437.html
C++ mingw и lib https://www.cyberforum.ru/ cpp/ thread151211.html
Как в mingw в коде подключить файл lib, #pragma comment(lib, "Gdi32.lib") не помогает. А то пытаюсь использовать SetTextColor и подобные функции, а без полезно без Gdi32.lib. Кто может подскажите. 		C++ Шилдт Полный справочник по С++ 4.0 Собственно ищу код к справочнику, о котором упоминалось на обложке. https://www.cyberforum.ru/ cpp/ thread150953.html
Мат в 32 хода
236 / 171 / 18
Регистрация: 10.09.2009
Сообщений: 1,096
05.09.2010, 10:22 0

Задачи для тренировки и лучшего понимания

05.09.2010, 10:22. Просмотров 419105. Ответов 1272
Метки (Все метки)

Ответ

Я 3тий день бъюсь над задачкой о коне... придумал такую штуку:
конь стоит на клетке 0,0.
перед тем как пойдти на новую клетку, он проверяет:
а) находятся ли её координаты на поле (на пример конь не может пойдти на клетку с координатами 8,9)
б) был ли он на ней.
после хода, координаты новой клетки впихаются в стек. старая помечается "пройденной".
если не один из возможных вариантов не удовлетворяет условий а и б, конь возвращается на предидущею клетку. а клетка с которой он вернулся помечается не пройденной и вытаскивается из стека. продолжаем повторять этот процес пока все клетки не будут пройдены. вот код. но не могу найти ошибку...
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

#include <iostream>
#include <cstdlib>
#include <conio.h>
using namespace std;
const int qoms=100;
short int desk[8][8][9];
class steps
{
    private:
        int cont[2][qoms];
        int l;
    public:
        steps();
        void addstep(int i, int k);
        void gotoback();
        void showthepath();
        int upper(int i);
};
steps::steps()
{
    for(int i=0;i<qoms;i++)
    {
        cont[0][i]=9;
        cont[1][i]=9;
    }
    l=0;
}
void steps::addstep(int i, int k)
{
    for(int j=qoms-1;j>0;j--)
    {
        cont[0][j]=cont[0][j-1];
        cont[1][j]=cont[1][j-1];
    }
    cont[0][0]=i;
    cont[1][0]=k;
    l++;
}
void steps::gotoback()
{
    for(int j=0;j<qoms-1;j++)
    {
        cont[0][j]=cont[0][j+1];
        cont[1][j]=cont[1][j+1];
    }
    for(int i=l;i<qoms;i++)
        cont[0][i]=cont[1][i]=9;
}
void steps::showthepath()
{
    for(int i=0;i<qoms;i++)
        if(cont[0][i]!=9)
            cout<<cont[0][i]<<","<<cont[1][i]<<" ";
}
int steps::upper(int i)
{
    if(i==0) return cont[0][0];
    else return cont[0][1];
}
bool isptogoto(int i, int k)
{
    if(i>=0 && i<8 && k>=0 && k<8)
        return true;
    else
        return false;
}
bool isdone()
{
    bool temp=true;
    for(int i=0;i<8;i++)
        for(int k=0;k<8;k++)
            if(desk[i][k][0]==false)
                temp=false;
    return temp;
}
int main()
{
    steps stps;
    char last;
    char lb;
    short int c=0;
    int qloq[2];
    qloq[0]=qloq[1]=0;
    stps.addstep(qloq[0],qloq[1]);
    int r;
    for(int i=0;i<8;i++)
        for(int l=0;l<8;l++)
            for(int k=0;k<9;k++)
                desk[i][l][k]=false;
    srand(time(NULL));
    while(!isdone())
    {
        if(isptogoto(qloq[0]+2, qloq[1]+1) && desk[qloq[0]][qloq[1]][1]==false && desk[qloq[0]+2][qloq[1]+1][0]==false)
        {
            stps.addstep(qloq[0]+2,qloq[1]+1);
            desk[qloq[0]][qloq[1]][1]=desk[qloq[0]+2][qloq[1]+1][0]=true;
            qloq[0]=qloq[0]+2;
            qloq[1]=qloq[1]+1;
            c++;
        } else if(isptogoto(qloq[0]+1, qloq[1]+2) && desk[qloq[0]][qloq[1]][2]==false && desk[qloq[0]+1][qloq[1]+2][0]==false)
        {
            stps.addstep(qloq[0]+1,qloq[1]+2);
            desk[qloq[0]][qloq[1]][2]=desk[qloq[0]+1][qloq[1]+2][0]=true;
            qloq[0]=qloq[0]+1;
            qloq[1]=qloq[1]+2;
            c++;
        } else if(isptogoto(qloq[0]-2, qloq[1]-1) && desk[qloq[0]][qloq[1]][3]==false && desk[qloq[0]-2][qloq[1]-1][0]==false)
        {
            stps.addstep(qloq[0]-2,qloq[1]-1);
            desk[qloq[0]][qloq[1]][3]=desk[qloq[0]-2][qloq[1]-1][0]=true;
            qloq[0]=qloq[0]-2;
            qloq[1]=qloq[1]-1;
            c++;
        } else if(isptogoto(qloq[0]-1, qloq[1]-2) && desk[qloq[0]][qloq[1]][4]==false && desk[qloq[0]-1][qloq[1]-2][0]==false)
        {
            stps.addstep(qloq[0]-1,qloq[1]-2);
            desk[qloq[0]][qloq[1]][4]=desk[qloq[0]-1][qloq[1]-2][0]=true;
            qloq[0]=qloq[0]-1;
            qloq[1]=qloq[1]-2;
            c++;
        } else if(isptogoto(qloq[0]-2, qloq[1]+1) && desk[qloq[0]][qloq[1]][5]==false && desk[qloq[0]-2][qloq[1]+1][0]==false)
        {
            stps.addstep(qloq[0]-2,qloq[1]+1);
            desk[qloq[0]][qloq[1]][5]=desk[qloq[0]-2][qloq[1]+1][0]=true;
            qloq[0]=qloq[0]-2;
            qloq[1]=qloq[1]+1;
            c++;
        } else if(isptogoto(qloq[0]+1, qloq[1]-2) && desk[qloq[0]][qloq[1]][6]==false && desk[qloq[0]+1][qloq[1]-2][0]==false)
        {
            stps.addstep(qloq[0]+1,qloq[1]-2);
            desk[qloq[0]][qloq[1]][6]=desk[qloq[0]+1][qloq[1]-2][0]=true;
            qloq[0]=qloq[0]+1;
            qloq[1]=qloq[1]-2;
            c++;
        } else if(isptogoto(qloq[0]+2, qloq[1]-1) && desk[qloq[0]][qloq[1]][7]==false && desk[qloq[0]+2][qloq[1]-1][0]==false)
        {
            stps.addstep(qloq[0]+2,qloq[1]-1);
            desk[qloq[0]][qloq[1]][7]=desk[qloq[0]+2][qloq[1]-1][0]=true;
            qloq[0]=qloq[0]+2;
            qloq[1]=qloq[1]-1;
            c++;
        } else if(isptogoto(qloq[0]-1, qloq[1]+2) && desk[qloq[0]][qloq[1]][8]==false && desk[qloq[0]-1][qloq[1]+2][0]==false)
        {
            stps.addstep(qloq[0]-1,qloq[1]+2);
            desk[qloq[0]][qloq[1]][8]=desk[qloq[0]-1][qloq[1]+2][0]=true;
            qloq[0]=qloq[0]-1;
            qloq[1]=qloq[1]+2;
            c++;
        } else
        {
            stps.gotoback();
            if(stps.upper(0)+2==qloq[0] && stps.upper(1)+1==qloq[1]) {desk[stps.upper(0)][stps.upper(1)][1]=true; r=1;}
            else if(stps.upper(0)+1==qloq[0] && stps.upper(1)+2==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][2]=true; r=2;}
            else if(stps.upper(0)-2==qloq[0] && stps.upper(1)-1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][3]=true; r=3;}
            else if(stps.upper(0)-1==qloq[0] && stps.upper(1)-1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][4]=true; r=4;}
            else if(stps.upper(0)-2==qloq[0] && stps.upper(1)+1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][5]=true; r=5;}
            else if(stps.upper(0)+1==qloq[0] && stps.upper(1)-2==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][6]=true; r=6;}
            else if(stps.upper(0)+2==qloq[0] && stps.upper(1)-1==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][7]=true; r=7;}
            else if(stps.upper(0)-1==qloq[0] && stps.upper(1)+2==qloq[1]){ desk[stps.upper(0)][stps.upper(1)][8]=true; r=8;}
            for(int t=0;t<9;t++)
                if(t!=r)
                    desk[qloq[0]][qloq[1]][t]=false;
            desk[qloq[0]][qloq[1]][0]=false;
            qloq[0]=stps.upper(0);
            qloq[1]=stps.upper(1);
            desk[qloq[0]][qloq[1]][0]=true;
            c--;
        }
        system("cls");
        for(int x=0;x<8;x++)
        {
            for(int y=0;y<8;y++)
                if(x==qloq[0] && y==qloq[1])
                    cout<<"O";
                else if(desk[x][y][0]==true)
                    cout<<"X ";
                else 
                    cout<<". ";
            cout<<"\n";
        }
        getch();
    }
    stps.showthepath();
    getch();
    return 0;
}
Добавлено через 57 минут
ЛЮДИ!!!! Мы тут мучеемся, а оказывается существует Правило Варнсдорфа.
Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.

Правило формулируется очень просто: следующий ход коня нужно делать на клетку, откуда существует наименьшее количество возможных ходов. Если клеток с одинаковым количеством ходом несколько, то можно выбрать любую.

На практике это реализуется, например, следующим образом. Перед каждым ходом коня вычисляется рейтинг ближайших доступных полей - полей, на которых конь еще не был, и на которые он может перейти за один ход. Рейтинг поля определяется числом ближайших доступных с него полей. Чем меньше рейтинг, тем он лучше. Потом делается ход на поле с наименьшим рейтингом (на любое из таковых, если их несколько), и так далее, пока есть куда ходить.

Эвристика всегда работает на досках от 5x5 до 76x76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.


Вернуться к обсуждению:
Задачи для тренировки и лучшего понимания
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 05.09.2010, 10:22
Готовые ответы и решения:

Элементарные программы, для лучшего понимания языка...
Здравствуйте. Вот сегодня решил что пора изучать с++. Есть пару задач. Начал решать и уже на первой...

Задачи для тренировки и лучшего понимания языка
Предлагаю в этой теме размещать задачи, которые помогут новичкам (и не только) более детально...

Литература для лучшего понимания сути программирования
Привет! Подскажите литературу, которая поможет разобраться в сути самого процесса программирования,...

Набор задачь для тренировки и улучшения понимания программирования
Добрый вечер всем. Если кто знает модскажите где можно найти подобный набор задачь...

1272
КиберФорум - форум программистов, компьютерный форум, программирование
Реклама - Обратная связь
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.