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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Sokolov
42 / 42 / 3
Регистрация: 04.01.2011
Сообщений: 125
#1

ЕГЭ Информатика - C++

13.05.2011, 15:57. Просмотров 1944. Ответов 10

На вход программы подаются прописные латинские буквы, ввод этих символов заканчивается точкой. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять, можно ли переставить эти буквы так, чтобы получился палиндром (палиндром читается одинаково слева направо и справа налево). Программа должна вывести ответ «Да» или «Нет», а в случае ответа «Да» – еще и сам полученный палиндром (первый в алфавитном порядке).
Пример входной строки:
GAANN
Пример выходных данных:
Да
ANGNA

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
#include<iostream>
using namespace std;
int main()
{int n=0,i,j,a[25],centr;
char c;
bool flag=false;
for(i=0;i<26;i++)
a[i]=0;
do
{
    cin>>c;
    if(c>='A'&&c<='Z')
    {
        a[c-'A']++;
    }
}
while(c!='.');
 
for(i=0;i<26;i++)
    if(a[i]%2==1)
{  flag=true; 
    centr=i;
    n++;
}
 
if(n>1||flag==false)
    cout<<"NO"<<endl;
else 
{
    cout<<"YES"<<endl;
    for(i=0;i<26;i++)
        if(a[i]!=0)
            for(j=0;j<a[i]/2;j++)
                cout<<(char)('A'+i);
    if(n==1)
        cout<<(char)(centr+'A');
    for(i=25;i>=0;i--)
        if(a[i]!=0)
            for(j=0;j<a[i]/2;j++)
                cout<<(char)(i+'A');
}
return 0;
}
Вроде работает, но выдает ошибку, "Stack around the variable 'a' was corrupted"
В чем ошибка?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2011, 15:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос ЕГЭ Информатика (C++):

ЕГЭ Информатика С2 - C++
Найти и вывести наименьший номер элемента массива, равного Х, или сообщение, что такого элемента нет. #include &lt;iostream&gt; using...

ЕГЭ Информатика С2 - C++
/*Опишите на русском языке или на одном из языков программирования алгоритм суммирования положительных элементов квадратной матрицы,...

ЕГЭ Информатика С4 - C++
Задача: После единых выпускных экзаменов по информатике в район пришла информация о том, какой ученик, какой школы сколько баллов...

ЕГЭ Информатика С2 (Массивы) - C++
Здравствуйте, решаю задачи для подготовки к ЕГЭ,все вроде бы легко,но проблема в том, что все ответы на Паскале. Решал такую задачу,...

Информатика - C++
Здравствуйте..Помогите пожалуйста с лабораторными по информатике?На языке С++?СМОЖЕТЕ КТО НИБУДЬ ПОМОЧЬ? Ребята вот ссылка лабы...

C4 ЕГЭ - C++
Нужно решить С4, прошу вашей помощи )) По каналу связи передаётся последовательность положительных целых чисел, все числа не...

10
Danvern
40 / 39 / 3
Регистрация: 22.06.2010
Сообщений: 415
Записей в блоге: 1
13.05.2011, 16:00 #2
потому что ты вылазишь за пределы массива a
надо всегда вот так задавать длину массива a[n + 1]
1
asics
Freelance
Эксперт С++
2848 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
13.05.2011, 16:10 #3
С помощью STL можно как-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <string>
 
bool is_pal(std::string &_s){
  return std::equal(_s.begin(), _s.end(), _s.rbegin());
}
 
int main(){
  std::string w("GAANN");
  std::sort(w.begin(), w.end());
  do
    if(is_pal(w)){
      std::cout << "Yes\n" << w << std::endl;
      return 1;
    }
  while(std::next_permutation(w.begin(), w.end()));
  std::cout << "No";
  return 0;
}
1
Sokolov
42 / 42 / 3
Регистрация: 04.01.2011
Сообщений: 125
13.05.2011, 16:52  [ТС] #4
Цитата Сообщение от Danvern Посмотреть сообщение
потому что ты вылазишь за пределы массива a
надо всегда вот так задавать длину массива a[n + 1]
почему?
там же 26 элементов, занчит и массив должен быть [26]

а, все понял, я [25] сдлелал
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
13.05.2011, 18:25 #5
Цитата Сообщение от Sokolov Посмотреть сообщение
C++
1
2
if(n>1||flag==false)
        cout<<"NO"<<endl;
Fail. А если все буквы чётное количество раз?
Цитата Сообщение от asics Посмотреть сообщение
С помощью STL можно как-то так
...
C++
1
while(std::next_permutation(w.begin(), w.end()));
По-моему, не удовлетворяет этому:
Напишите эффективную по времени работы и по используемой памяти программу
Хотя про время работы формулировка такая непонятная...
0
ValeryLaptev
Эксперт С++
1042 / 821 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
13.05.2011, 18:46 #6
ИМХО, нужно 26 счетчиков - массив из 26 элементов. Буква - индекс.
За ОДИН просмотр строки вычисляются все счетчики. Условие палиндрома: НЕ БОЛЕЕ ОДНОГО НЕЧЕТНОГО числа среди счетчиков.
0
Нач_физик
2 / 2 / 0
Регистрация: 12.02.2011
Сообщений: 49
13.05.2011, 19:35 #7
Вообще ни разу не правильно.
1. Условие воспроизведено не верно. Это задание с4 в нем на вход подается СТРОКА и ТОЛЬКО СТРОКА символов, ни какого посимвольного ввода. Потому, что в С4 проверяется способность работы со сторковым типом данных ( извлекать из него нужную информацию, по необходимости конвертировать в числовые типы и т.д) если будет посимвольный ввод то дальше работу проверять не будут.

2. Алгоритм должен строится на идее паллиндрома - если количество символов в слове четное, то половина символов должна иметь пару, если количество символов не четное (n) то (n-1)/2 символов должно иметь пару - иначе паллиндром не возможен.
При поиске пар одновременно формируем новую строку( изначально пустую) в начало и конец которой вставляем члены пары, вторую пару ставим на второе и предпоследее место и т.д. одновременно удаляем из исходной строки найденные пары пока она не закончится( такое возможно только если да и количество четное) или не закончатся пары( тогда если в строке осталось более 1 символа - паллиндром не возможен, если 1 и количество нечетное вставить его в середину на оставшееся место и вывести "да" и получившийся паллиндром, соответственно, если 1 и количество четное, то нет)
0
asics
Freelance
Эксперт С++
2848 / 1783 / 144
Регистрация: 09.09.2010
Сообщений: 3,841
13.05.2011, 19:38 #8
Цитата Сообщение от Somebody Посмотреть сообщение
По-моему, не удовлетворяет этому:
Согласен. Я только показал еще вариант, не утверждая, что он ефективный по времени.
0
Нач_физик
2 / 2 / 0
Регистрация: 12.02.2011
Сообщений: 49
13.05.2011, 19:41 #9
И всё это ,поиск и формирование паллиндрома, в одном цикле , если будет два цикла или цикл в цикле - минус балл ибо не эфективный алгоритм, обявите массив для хранения пар - минус балл ибо можно и без него и тд . после цикла вывести ответ.
0
Somebody
2791 / 1602 / 147
Регистрация: 03.12.2007
Сообщений: 4,199
Завершенные тесты: 1
14.05.2011, 12:38 #10
Цитата Сообщение от Нач_физик Посмотреть сообщение
1. Условие воспроизведено не верно. Это задание с4 в нем на вход подается СТРОКА и ТОЛЬКО СТРОКА символов, ни какого посимвольного ввода. Потому, что в С4 проверяется способность работы со сторковым типом данных ( извлекать из него нужную информацию, по необходимости конвертировать в числовые типы и т.д) если будет посимвольный ввод то дальше работу проверять не будут.
Ё-моё. Если это на самом деле так, если бы я писал ЕГЭ по информатике, кажется, у меня была бы двойка...
А если строка стопятьсот символов, то чтение целой строки можно посчитать неэффективным по использованию памяти.
Метки: школоло
...
0
lamed
297 / 297 / 71
Регистрация: 07.05.2011
Сообщений: 592
14.05.2011, 20:28 #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
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
// [url]http://kpolyakov.narod.ru/school/ege.htm[/url]
// На вход программы подаются прописные латинские буквы,
// ввод этих символов заканчивается точкой.
// Определять, можно ли переставить эти буквы так, чтобы получился палиндром
// Программа должна вывести ответ «Да» или «Нет»,
// а в случае ответа «Да» – еще и сам полученный палиндром
// (первый в алфавитном порядке).
// Пример входной строки: GAANN
// Пример выходных данных: Да  ANGNA
// G++/Code::Blocks
// lamed, 14.05.2011
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    char s[100];
    bool cond;
    int i, j, len;
 
    cin >> s;
    for (j=0;s[j]!='.'; j++)
        ;
    len=j;
    j--;
    i=0;
    cond = true;
    while (i<j && cond) {
        if (s[i]!=s[j]) {
            int k=i+1;
            while (k<j && s[i]!=s[k])
                k++;
            if (k<j) {
                char tmp = s[k];
                s[k] = s[j];
                s[j] = tmp;
            }
        else
            cond = false;
        }
        if (cond) {
            i++;
            j--;
        }
    }
 
    if (cond)
    {
        s[len]='\0';
        cout << "yes " << s << endl;
    }
    else
        cout << "no" << endl;
    return 0;
}
1
14.05.2011, 20:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2011, 20:28
Привет! Вот еще темы с ответами:

Информатика 8-9 классы - C++
Народ! Срочно нудна помощь! Информатика 8-9 класс! Пожалуйста, кто сможет помочь=))

Информатика ! очень нужно - C++
Дано натуральное число k . Напечатать k-ую цифру (не число!) последовательности из идущих подряд чисел Фибоначчи. 112358132134......

С++ Одна из задач ЕгЭ С4 - C++
Задача С4 На вход в программе подаются сведения о студентах с 1-го по 5-й курс некоторого вуза. В первой строке сообщается количество...

Кодировка в консоли (на ЕГЭ) - C++
В этом году буду писать экзамен, но дело в том, что в visual studio setlocale(LC_ALL,&quot;Rus&quot;); не приводит ни к чему (знаю, что в самой...


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

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

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