42 / 42 / 13
Регистрация: 04.01.2011
Сообщений: 125
1

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

13.05.2011, 15:57. Показов 4546. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2011, 15:57
Ответы с готовыми решениями:

ЕГЭ Информатика С2
Найти и вывести наименьший номер элемента массива, равного Х, или сообщение, что такого элемента...

ЕГЭ Информатика С2
/*Опишите на русском языке или на одном из языков программирования алгоритм суммирования...

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

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

10
41 / 40 / 5
Регистрация: 22.06.2010
Сообщений: 415
Записей в блоге: 1
13.05.2011, 16:00 2
потому что ты вылазишь за пределы массива a
надо всегда вот так задавать длину массива a[n + 1]
1
Freelance
Эксперт С++
2886 / 1821 / 356
Регистрация: 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
42 / 42 / 13
Регистрация: 04.01.2011
Сообщений: 125
13.05.2011, 16:52  [ТС] 4
Цитата Сообщение от Danvern Посмотреть сообщение
потому что ты вылазишь за пределы массива a
надо всегда вот так задавать длину массива a[n + 1]
почему?
там же 26 элементов, занчит и массив должен быть [26]

а, все понял, я [25] сдлелал
0
2831 / 1640 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
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
Эксперт С++
1067 / 846 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
13.05.2011, 18:46 6
ИМХО, нужно 26 счетчиков - массив из 26 элементов. Буква - индекс.
За ОДИН просмотр строки вычисляются все счетчики. Условие палиндрома: НЕ БОЛЕЕ ОДНОГО НЕЧЕТНОГО числа среди счетчиков.
0
2 / 2 / 1
Регистрация: 12.02.2011
Сообщений: 49
13.05.2011, 19:35 7
Вообще ни разу не правильно.
1. Условие воспроизведено не верно. Это задание с4 в нем на вход подается СТРОКА и ТОЛЬКО СТРОКА символов, ни какого посимвольного ввода. Потому, что в С4 проверяется способность работы со сторковым типом данных ( извлекать из него нужную информацию, по необходимости конвертировать в числовые типы и т.д) если будет посимвольный ввод то дальше работу проверять не будут.

2. Алгоритм должен строится на идее паллиндрома - если количество символов в слове четное, то половина символов должна иметь пару, если количество символов не четное (n) то (n-1)/2 символов должно иметь пару - иначе паллиндром не возможен.
При поиске пар одновременно формируем новую строку( изначально пустую) в начало и конец которой вставляем члены пары, вторую пару ставим на второе и предпоследее место и т.д. одновременно удаляем из исходной строки найденные пары пока она не закончится( такое возможно только если да и количество четное) или не закончатся пары( тогда если в строке осталось более 1 символа - паллиндром не возможен, если 1 и количество нечетное вставить его в середину на оставшееся место и вывести "да" и получившийся паллиндром, соответственно, если 1 и количество четное, то нет)
0
Freelance
Эксперт С++
2886 / 1821 / 356
Регистрация: 09.09.2010
Сообщений: 3,841
13.05.2011, 19:38 8
Цитата Сообщение от Somebody Посмотреть сообщение
По-моему, не удовлетворяет этому:
Согласен. Я только показал еще вариант, не утверждая, что он ефективный по времени.
0
2 / 2 / 1
Регистрация: 12.02.2011
Сообщений: 49
13.05.2011, 19:41 9
И всё это ,поиск и формирование паллиндрома, в одном цикле , если будет два цикла или цикл в цикле - минус балл ибо не эфективный алгоритм, обявите массив для хранения пар - минус балл ибо можно и без него и тд . после цикла вывести ответ.
0
2831 / 1640 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
14.05.2011, 12:38 10
Цитата Сообщение от Нач_физик Посмотреть сообщение
1. Условие воспроизведено не верно. Это задание с4 в нем на вход подается СТРОКА и ТОЛЬКО СТРОКА символов, ни какого посимвольного ввода. Потому, что в С4 проверяется способность работы со сторковым типом данных ( извлекать из него нужную информацию, по необходимости конвертировать в числовые типы и т.д) если будет посимвольный ввод то дальше работу проверять не будут.
Ё-моё. Если это на самом деле так, если бы я писал ЕГЭ по информатике, кажется, у меня была бы двойка...
А если строка стопятьсот символов, то чтение целой строки можно посчитать неэффективным по использованию памяти.
Метки: школоло
...
0
298 / 298 / 150
Регистрация: 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.05.2011, 20:28
Помогаю со студенческими работами здесь

Егэ информатика 27 задача
Спрошу коротко , почему у меня ошибка на 18 строчке ? #include &lt;iostream&gt; using namespace std ;...

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

информатика
с чего начать изучать информатику ?

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

ЕГЭ Вариант 15 №19
На вход дается массив из десяти цифр 98, задача определить значение s после выполнения программы....

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru