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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Rustam
12 / 12 / 3
Регистрация: 05.09.2009
Сообщений: 440
#1

Найдите два слова с наилучшей рифмой и еще две задачи. - C++

26.09.2009, 21:22. Просмотров 1150. Ответов 3
Метки нет (Все метки)

1).Рифмы
Дан текст (набор слов). Найдите в нем два слова с наилучшей рифмой. Наилучшей будем считать рифму, когда у пары слов совпадает наибольшее число букв с конца.
Формат входных данных

Первая строчка входных данных содержит натуральное число n, 2<=n<=10000. Затем идет n различных строк, каждая из которых содержит одно слово (слова могут состоять из латинских и русских букв в кодировке KOI-8, заглавные и строчные буквы считаются различными).
Формат выходных данных

Программа должна вывести в одной строчке число последних совпадающих букв в наилучшей рифме, затем (через пробел) два слова, образующих эту рифму. Если существует несколько наилучших рифм, то программа должна вывести только одну (любую) пару из них. Если никакие два слова входного текста не рифмуются между собой, программа должна вывести одно число 0.
Примеры
Входные данные:
2
олимпиада
программирование
Выходные данные:
0
Входные данные:
8
зеленый
том
ученый
кругом
направо
заводит
налево
говорит
Выходные данные:
4 зеленый ученый


2).Значение выражения
Входная строка содержит арифметическое выражение, которое может содержать целочисленные константы, скобки, бинарные операторы +, -, *, /, унарные операторы + и -. Вычислите значение этого выражения.
Формат входных данных

Во входных данных содержится единственная строка, содержащая цифры, знаки арифметических операций, круглые скобки. Строка не содержит пробелов. Все целочисленные константы не превосходят по модулю 109. Арифметическое выражение корректно, никакие два знака арифметической операции не идут подряд (то есть унарный оператор не следует после бинарного), числа не содержат лидирующих нулей. Гарантируется, что результат работы, а также результаты всех промежуточных вычислений, не превосходят 109. Длина строки не превосходит 1000 символов.

Все действия выполняются слева направо. Сначала выполняются умножения и деления, затем – сложения и вычитания. Деление выполняется нацело по правилам компилятора g++.
Формат выходных данных

Программа должна вывести значение данного выражения. При возникновении деления на ноль, программа должна вывести слово Error.
Примеры
Вход Выход
2-(7+3*4)/5 -1


1/(1-1) Error


3).Удаление клеток
Из прямоугольного листа бумаги (M строк, N столбцов) удалили некоторые клетки. Определите, на сколько кусков распадается оставшаяся часть листа. Две клетки не распадаются, если они имеют общую сторону.
Формат входных данных

Первая строка входных данных содержит числа M и N, не превосходящие 1000. Далее идет M строк по N символов, состоящих из символов # и . (точка). Если клетка не была вырезана, этому соответствует знак #, если вырезана – точка.
Формат выходных данных

Программа должна вывести единственное целое число – количество частей, на которое распадется лист бумаги.
Пример
Вход
4 8
#.##.#.#
......##
#.###.##
##.##.##

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

в ходе решения задачи возникли еще вопросы ) C++
Ввести строку и два слова, заменить все вхождения первого слова на второе C++
C++ Нужно написать программу в с/с++, которая определяет являются ли 2 введенных с клавиатуры слова рифмой
C++ Найдите все слова в предложении, содержащие по две буквы М, не стоящие рядом, и определите их количество
Нужно еще два способа (вывести введенное слово наоборот) C++
C++ В заданной строке выбрать те слова,в которых первая буква этого слова встречается еще хоть один раз
C++ Дана строка, в которой слова разделены одним пробелом. Найдите и выведите все слова указанной длины
C++ Найдите среди точек две такие, что угол AOB минимальный
C++ Дано предложение. В нем только два слова одинаковые. Найти эти слова
C++ Дано предложение, где два слова различны. Найти эти слова
Модифицированный метод наилучшей пробы C++
C++ Две задачи

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Search..
Заказ софта
340 / 185 / 10
Регистрация: 26.05.2009
Сообщений: 863
27.09.2009, 02:11     Найдите два слова с наилучшей рифмой и еще две задачи. #2
Задачи легкие. Сделал первую не так, как там было написано, но смысл тот же.
Не нравится тупость с массивами - замени векторами, нравится - на здоровье..

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
#include <iostream>
#include <fstream>
 
class find_rifm
{
public:
    find_rifm(char* dir)
    { strcpy(path, dir);
      ifFile.open(dir); }
    ~find_rifm()
    { ifFile.close();   }
 
    bool startFind(char*, char*);
private:
    char path[256];
    char word[64];
    char words[100][64];
    std::ifstream ifFile;
};
 
bool find_rifm::startFind(char* chOne, char* chTwo)
{
    if(ifFile.fail())
        return false;
 
    system("title Search rhymes...\n");
    int flg = 0;
 
    do
    {
        ifFile >> words[flg];
        flg++;
    } while(!ifFile.eof());
 
    int size = flg, symbol = 0, max = 1, lenOne = 0, lenTwo = 0;
 
    for(int i = 0; i < size; i++)
    {
        lenOne = (int)strlen(words[i]);
        for(int j = i + 1; j < size; j++)
        {
            lenTwo = (int)strlen(words[j]);
            while(!strncmp(strrev(words[i]), strrev(words[j]), symbol + 1))
            {
                if(symbol == std::min <int> (lenOne, lenTwo))
                    break;
                else
                {
                    std::cout << "\n////////////////////////////////////\n";
                    std::cout << "/// " << strrev(words[i]) << " : " << strrev(words[j]) << "\n";
                    std::cout << "/// ----------------------\n";
                    std::cout << "/// Identical symbols: " << symbol++ + 1 << "\n";
                    std::cout << "////////////////////////////////////\n";
                }
            }
 
            if(symbol > max)
            {
                max = symbol;
                strcpy(chOne, strrev(words[i]));
                strcpy(chTwo, strrev(words[j]));
            }
 
            symbol = 0;
        }
    }
 
    std::cout << "\n\n------------------------------------------------------------\n";
    std::cout << "--- Result for file \'" << path << "\'\n";
    std::cout << "------------------------------------------------------------\n\n";
    system("title Find completed.");
    return true;
}
 
int main(int argc, char* argv[])
{
    char dir[128] = "\0", one[64] = "\0", two[64] = "\0";
 
    if(argc == 2)
        strcpy(dir, argv[1]);
    else
    {
        std::cout << "Enter file words:\n> ";
        std::cin  >> dir;
    }
 
    find_rifm myRifm(dir);
 
    if(myRifm.startFind(one, two))
    {
        std::cout << "[One word]: " << one << "\n";
        std::cout << "[Two word]: " << two << "\n";
    }
    else
    {
        system("title ERROR");
        std::cout << "File don't open...\n";
    }
 
    return 0;
}
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 15:31     Найдите два слова с наилучшей рифмой и еще две задачи. #3
Олимпиадные задачи

Задача про рифмы
http://cntt.ru/olimp/Tyri/PRAKTIKA/P...limp_progr.doc

Вторая про выражения
http://server.179.ru/tasks/olymp/077.html

Третья про клетки
http://server.179.ru/tasks/olymp/072.html
kravam
быдлокодер
1695 / 874 / 44
Регистрация: 04.06.2008
Сообщений: 5,340
30.09.2009, 17:33     Найдите два слова с наилучшей рифмой и еще две задачи. #4
Автор, держи третью задачу.
Пихай файлы в одну папку и компилируй main.cpp На DEV C++ работат, под остальные среды подгоняй сам.
Ввод, как и предусмотрено в условии

10 10
###...###.
..##.###..
##..###..#
####...##.
...####.##
####.####.
..#.#.#...
.##.###...
#.##....#.
###...####

Выдаёт 5

Слабые места:

1) вогнал в прогу бесконечный цикл
whilw (1) {}, из которого не могу выбраться. Страшного ничего, просто консоль придётся закрывать
мышью, если понадобится.

2) Массивы у меня динамические, по идее надо как-то память свобождать в конце каждого цикла, но я не
знаю, как

3) По окончании работы весь массив представляет из себя одни точки. Так что если надо сохранить-
сохраняй заранее.

Прога проходит по всем элементам массива, пока не наткнётся на #. После этого она вызывет
функцию rekursFunc () (определена в файле rekursFunc.cpp), которая рекурсивно проходит всем решёткам ЭТОГО блока решёток, превращая их в точки.
Соответственно, количество блоков увеличивается на 1.

Функция rekursFunc (), в свою очередь, по заходу в очередную клетку, вызывает другую функцию
zahod_v_kletku () (определена в "zahod_v_kletku.cpp"), которая определяет, куда идти дальше- прямо, налево или направо (прямо считается направление, откуда мы пришли)

Если идти некуда, очередная ветвь rekursFunc () закончилась.

В файле "globalnperemenie.h" глобальные переменные

Тестируй и присылай значения, которые не канают. Я буду исправлять. Но так-то я тестировал.
...Короче, я не знаю, как делать ссылки на файлы. Лови так.
Первый файл основной, потом заголовочный и два *cpp


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
#include <iostream>
using namespace std;
 
 
#include "globalnperemenie.h"
#include "rekursFunc.cpp" 
 
 
 
 
 
 
 
int main() {
 
while (1) {
 
 kolichestvo_blokov= 0;
 
 
 cout<<"Вводи количество столбцов и строк через пробел и массив потом"<<endl;
 fflush (stdin);
 cin>> M;
 cin>> N;
 
 //Массив тот самый
 char** array= new char* [M] ;
 
 //а ЭТО копия. С ней и будем работать, а array изменится в следующем цикле
 char** array_osn= array;
 
 //Это выделение памяти
 for (int i= 0; i< M; i++) {
  *array= new char[N];
   array++;
 }
 
 
 //Заполнение массива
 for (int i= 0; i< M; i++) {
  getchar ();
  for (int j= 0; j< N; j++) {
   array_osn [i] [j]= getchar ();
  }
 }
 
 
 
 
 for (int i= 0; i< M; i++) {
  for (int j= 0; j< N; j++) {
   if (array_osn [i] [j]== '#') {
 
    //Всякий раз если в функции rekursFunc если идёт работа с ПЕРВОЙ клеткой блока
    //(грубо говоря, если plus_ili_net==1) то глобальная переменная kolichestvo_blokov
    //инкременируется
    plus_ili_net= true;
 
    //сложность из-за того, что если это нулевая клетка може быть!
    rekursFunc (array_osn  ,i, (i==0 && j==0)?-1: j-1, i, j);
     
   }   
  }
 }
 
 
 cout<<"количество таких блоков равно"<<endl;
 
} 
 
 getchar ();
 getchar ();
 return 0;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <Windef.h>
 
//эТО СООТВЕТСВЕННО количество строк и столбцов массива
int M, N;
 
 
//Эта штука тоже должна быть доступна в функциях. Тоже глобальна поэтому. 
int kolichestvo_blokov= 0;
 
 
//Инкременируем kolichestvo_blokov в зависимомти от значения этой переменной
BOOL plus_ili_net;

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
#include "zahod_v_kletku.cpp"
 
//Параметры  i_tek,  j_tek есть параметры текущей клетки, i_pred и j_pred предыдущей
void rekursFunc (char** array  , int i_pred, int j_pred, int i_tek, int j_tek) {
 //Так, зашли в клетку. Если это первая клетка блока, то инкременируем kolichestvo_blokov;
 if (plus_ili_net) {
  kolichestvo_blokov++;
 }
 plus_ili_net=0;
  //Теперь нам нужно поийти дальше- налево, прямо или направо.
 //Но куда имено?
 //Вот для этой цели существуют такие переменые
 
  //пОКА ЧТО ЭТИ ПЕРЕММЕННЫЕ УСТАНОВЛЕНЫ В НУЛЬ. тО есть никуда нельхя идти (по умолчанию)
 //ТАК ли это на самом дее, нам предстоит выяснить с помощью функции zahod_v_kletku
 
 BOOL poidom_nalevo= false;  
 BOOL poidom_pramo= false;  
 BOOL poidom_napravo= false;  
 
 //По выходу из этой функции переменным, отвечающим за то, куда мы пойдём будут присвоено либо
 // false либо true
 zahod_v_kletku (array, i_pred, j_pred, i_tek, j_tek, &poidom_nalevo, &poidom_pramo, &poidom_napravo);
 
 //Теперь смотрим, куда можно пойти и туда идём. Но перед этим ОБЯЗАТЕЛЬНО превращаем
 //текущую клетку в точку
 array [i_tek] [j_tek]= '.';
 
 if (poidom_nalevo) {
  //Теперь надо разобраться с двумя вторыми аргументами
  //Это если движение было по горизонтали
  if (i_pred== i_tek) {
   //Если двигались слева направл
   if (j_pred<j_tek) {
    rekursFunc (array,i_tek, j_tek, i_tek-1, j_tek);
   }
 
   //аЭТО Если справа налево
   else {
    rekursFunc (array, i_tek, j_tek, i_tek+1, j_tek);
   }
  }
 
  //А это по ветикали
  else {
 
   //Если двигались снизу вверх 
   if (i_pred>i_tek) {
    rekursFunc (array, i_tek, j_tek, i_tek, j_tek- 1);
   }
 
   //Если двигались сверху вниз
   if (i_pred<i_tek) {
    rekursFunc (array, i_tek, j_tek, i_tek, j_tek+ 1);
   }
 
  }
 }
 
 if (poidom_pramo) {
  //Если движение било по горизотали
  if (i_pred== i_tek) {
   //Если движение было слева направо 
   if (j_pred< j_tek) {
    rekursFunc (array, i_tek, j_tek, i_tek, j_tek+ 1);
   }
 
   //Это если справа налево
   else {
    rekursFunc (array, i_tek, j_tek, i_tek, j_tek- 1);
   }
  }
  
  //А это по вертикали
  else {
   //Если движение было снизу вверх
   if (i_pred>i_tek) {
    rekursFunc (array, i_tek, j_tek, i_tek-1, j_tek);
   }
 
   //Cверху вниз
   else {
    rekursFunc (array, i_tek, j_tek, i_tek+ 1, j_tek);
   }
  }
 }
 
 if (poidom_napravo) {
  //Если движение было по горизонтали
  if (i_pred== i_tek) {
   //Если движение было cслева направо
   if (j_pred< j_tek) {
    rekursFunc (array, i_tek, j_tek, i_tek+ 1, j_tek);
   }
 
   //справа налево
   else {
    rekursFunc (array, i_tek, j_tek, i_tek- 1, j_tek);
   }
  }
 
  //А это по вертиикали
  else {
   //Снизу вверх
   if (i_pred>i_tek) {
    rekursFunc (array, i_tek, j_tek, i_tek, j_tek+ 1);
   }
 
   //Сверху вниз
   else {
    rekursFunc (array, i_tek, j_tek, i_tek, j_tek- 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
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
#include <Windef.h>
 
//Эта будет вызываться всякий раз, когда будет 
//совершён заход в клетку
//эта функция определяет, куда можно из этой клетки идти- налево, прямо или направо
//ИЛИ в несколько напраелений. Назад идти нельзя, так предполагается, что именно оттуда мы и пришли.
//Параметры функции это координаты предыдущей клетк,
//координаты настоящей клетки и адреса трёх переменных типа BOOL
void zahod_v_kletku (char** array, int i_ot, int j_ot, int i_n, int j_n, BOOL* poidom_nalevo, BOOL* poidom_pramo, BOOL* poidom_napravo ) {
 
 //Прежде всего мы должны выяснить, пойдём ли мы мз этой клетки налево,направо или прямо
 //Направление считается по ходу захода в клетку
 
  
 //эТО значит, что мы зашли сюда по горизонтали
 if (i_ot== i_n) {
 
 
 
//++++++++++++++++++++++++++++++++++Здесь мы выясняем, пойдём налево или нет+++++++++++++++++++++++
  //Это знначит, что мы сдвинулись слева направо
  if (j_ot< j_n) {
   if (i_ot) {
     //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n- 1] [j_n]== '#') {
     *poidom_nalevo= true;
    } 
   }
  }
 
  //а Это ссправа налево
  else {
   if (i_ot!= M-1) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n+ 1] [j_n]== '#') {
     *poidom_nalevo= true;
    }
   }
  }
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
 
//++++++++++++++++++++++++++++++++++Здесь мы выясняем, пойдём прямо или нет+++++++++++++++++++++++
  //Это знначит, что мы сдвинулись слева направо
  if (j_ot< j_n) {
   if (j_n!= N-1) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n] [j_n+ 1]== '#') {
     *poidom_pramo= true;
    }
   }
  }
 
  //а Это справа налево
  else {
   if (j_n) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n] [j_n- 1]== '#') {
     *poidom_pramo= true;
    }
   }
  }
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
 
//++++++++++++++++++++++++++++++++++Здесь мы выясняем, пойдём мы направо или нет+++++++++++++++++++++++
  //Это знначит, что мы сдвинулись слева направо
  if (j_ot< j_n) {
   if (i_ot!= M-1) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n+ 1] [j_n]== '#') {
     *poidom_napravo= true;
    }
   }
  }
 
  //а Это справа налево
  else {
   if (i_n) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n- 1] [j_n]== '#') {
     *poidom_napravo= true;
    }
   }
  }
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 }
 
 
 //wwwwwwwwwwwwwwwwwwwwwwwwwwwwwа ЭТО значит, что по вертикалиwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
 else {
 
//++++++++++++++++++++++++++++++++++Здесь мы выясняем, пойдём налево или нет+++++++++++++++++++++++
  //Это знначит, что мы сдвинулись снизу вверх
  if (i_ot> i_n) {
   if (j_ot) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n] [j_n- 1]== '#') {
     *poidom_nalevo= true;
    }
   }
  }
 
  //а Это сверху вниз
  else {
   if (j_ot!= N-1) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n] [j_n+ 1]== '#') { 
     *poidom_nalevo= true;
     }
   }
  }
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
 
//++++++++++++++++++++++++++++++++++Здесь мы выясняем, пойдём прямо или нет+++++++++++++++++++++++
  //Это знначит, что мы сдвинулись снизу вверх
  if (i_ot> i_n) {
   if (i_n) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n- 1] [j_n]== '#') {
     *poidom_pramo= true;
    }
   }
  }
 
  //а Это сверху вниз
  else {
   if (i_n!= M-1) {
    //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n+ 1] [j_n]== '#') {
     *poidom_pramo= true;
    }
   }
  }
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 
 
//++++++++++++++++++++++++++++++++++Здесь мы выясняем, пойдём мы направо или нет+++++++++++++++++++++++
  //Это знначит, что мы сдвинулись снизу вверх
  if (i_ot> i_n) {
   if (j_ot!= N-1) {
     //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n] [j_n+ 1]== '#') {
     *poidom_napravo= true;
    }
   }
  }
 
  //а Это сверху вниз
  else {
   if (j_ot) {
     //Идти можно, клетка не скраю. Последнее- выясняем значение клетки, на которую пойдём;
    if (array [i_n] [j_n- 1]== '#') {
     *poidom_napravo= true;
    }
   }
  }
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
      
 }
 
}
Yandex
Объявления
30.09.2009, 17:33     Найдите два слова с наилучшей рифмой и еще две задачи.
Ответ Создать тему
Опции темы

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