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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.71
Sokolov
 Аватар для Sokolov
42 / 42 / 3
Регистрация: 04.01.2011
Сообщений: 125
13.05.2011, 15:57     ЕГЭ Информатика #1
На вход программы подаются прописные латинские буквы, ввод этих символов заканчивается точкой. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, 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"
В чем ошибка?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2011, 15:57     ЕГЭ Информатика
Посмотрите здесь:

C++ Информатика
ЕГЭ Информатика С2 C++
ЕГЭ Информатика С2 (Массивы) C++
ЕГЭ Информатика С2 C++
C++ ЕГЭ Информатика С4
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Danvern
 Аватар для Danvern
40 / 39 / 3
Регистрация: 22.06.2010
Сообщений: 415
Записей в блоге: 1
13.05.2011, 16:00     ЕГЭ Информатика #2
потому что ты вылазишь за пределы массива a
надо всегда вот так задавать длину массива a[n + 1]
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
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;
}
Sokolov
 Аватар для Sokolov
42 / 42 / 3
Регистрация: 04.01.2011
Сообщений: 125
13.05.2011, 16:52  [ТС]     ЕГЭ Информатика #4
Цитата Сообщение от Danvern Посмотреть сообщение
потому что ты вылазишь за пределы массива a
надо всегда вот так задавать длину массива a[n + 1]
почему?
там же 26 элементов, занчит и массив должен быть [26]

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

2. Алгоритм должен строится на идее паллиндрома - если количество символов в слове четное, то половина символов должна иметь пару, если количество символов не четное (n) то (n-1)/2 символов должно иметь пару - иначе паллиндром не возможен.
При поиске пар одновременно формируем новую строку( изначально пустую) в начало и конец которой вставляем члены пары, вторую пару ставим на второе и предпоследее место и т.д. одновременно удаляем из исходной строки найденные пары пока она не закончится( такое возможно только если да и количество четное) или не закончатся пары( тогда если в строке осталось более 1 символа - паллиндром не возможен, если 1 и количество нечетное вставить его в середину на оставшееся место и вывести "да" и получившийся паллиндром, соответственно, если 1 и количество четное, то нет)
asics
Freelance
Эксперт C++
 Аватар для asics
2838 / 1775 / 144
Регистрация: 09.09.2010
Сообщений: 3,842
13.05.2011, 19:38     ЕГЭ Информатика #8
Цитата Сообщение от Somebody Посмотреть сообщение
По-моему, не удовлетворяет этому:
Согласен. Я только показал еще вариант, не утверждая, что он ефективный по времени.
Нач_физик
2 / 2 / 0
Регистрация: 12.02.2011
Сообщений: 49
13.05.2011, 19:41     ЕГЭ Информатика #9
И всё это ,поиск и формирование паллиндрома, в одном цикле , если будет два цикла или цикл в цикле - минус балл ибо не эфективный алгоритм, обявите массив для хранения пар - минус балл ибо можно и без него и тд . после цикла вывести ответ.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
14.05.2011, 12:38     ЕГЭ Информатика #10
Цитата Сообщение от Нач_физик Посмотреть сообщение
1. Условие воспроизведено не верно. Это задание с4 в нем на вход подается СТРОКА и ТОЛЬКО СТРОКА символов, ни какого посимвольного ввода. Потому, что в С4 проверяется способность работы со сторковым типом данных ( извлекать из него нужную информацию, по необходимости конвертировать в числовые типы и т.д) если будет посимвольный ввод то дальше работу проверять не будут.
Ё-моё. Если это на самом деле так, если бы я писал ЕГЭ по информатике, кажется, у меня была бы двойка...
А если строка стопятьсот символов, то чтение целой строки можно посчитать неэффективным по использованию памяти.
Метки: школоло
...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2011, 20:28     ЕГЭ Информатика
Еще ссылки по теме:

C++ Информатика 8-9 классы
C++ C4 ЕГЭ
задача с4 егэ :( C++

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

Или воспользуйтесь поиском по форуму:
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;
}
Yandex
Объявления
14.05.2011, 20:28     ЕГЭ Информатика
Ответ Создать тему

Метки
егэ, школоло
Опции темы

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