0 / 0 / 0
Регистрация: 11.04.2018
Сообщений: 8
1

Определить, можно ли вторую строку получить путем перестановки символов первой строки

25.04.2018, 16:24. Показов 5104. Ответов 11
Метки нет (Все метки)

Даны два символьных строки, содержащие только символы латинского алфавита. Создать программу, которая определит, можно ли вторую строчку получить путем перестановки символов первой строки. В результате программа должна вывести "Yes" или "No".
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
25.04.2018, 16:24
Ответы с готовыми решениями:

Можно ли вторую строчку получить путем перестановки символов первой строки?
Даны два символьных строки, содержащие только символы латинского алфавита. Создать программу,...

Можно ли из исходной строки путём перестановки литер получить вторую строку?
3.Пусть даны две строки str1 и str2. Необходимо выяснить, можно ли из str1 путём перестановки литер...

Выяснить, можно ли из строки str1 получить строку str2 путем перестановки символов
даны две строки str1 и str2 .Выяснить,можно ли из строки str1 получить строку str2 путем...

Даны 2 строки. определить можно ли, переставляя символы в первой строке, получить вторую строку. Строки вводят
Даны 2 строки. определить можно ли, переставляя символы в первой строке, получить вторую строку....

11
Объявлятель переменных
1201 / 389 / 316
Регистрация: 24.09.2011
Сообщений: 1,229
27.04.2018, 10:57 2
Pascal
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
function GetSortedString(S: string): string;
var
  i, j: integer;
  ch: char;
begin
  for i := 1 to length(S)-1 do
    for j := i+1 to length(S) do
      if S[i] > S[j] then
      begin
        ch := S[i];
        S[i] := S[j];
        S[j] := ch;
      end;
  GetSortedString := S;
end;
 
function IsAnagram(const S1, S2: string): boolean;
begin
  IsAnagram := GetSortedString(S1) = GetSortedString(S2);
end;
 
var
  S1, S2: string;
begin
  write('Введите первую строку: '); readln(S1);
  write('Введите вторую строку: '); readln(S2);
  if IsAnagram(S1, S2) then
    writeln('Строки имеют одинаковый набор символов')
  else
    writeln('Строки имеют разный набор символов')
end.
0
4951 / 2559 / 2310
Регистрация: 10.12.2014
Сообщений: 9,812
27.04.2018, 11:32 3
SpBerkut, что-то сильно сложно…
Да и не отвечает требованиям:
Цитата Сообщение от Blogs Посмотреть сообщение
В результате программа должна вывести "Yes" или "No".
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var s1,s2 : String; i : Integer;
begin
  ReadLn(s1);
  ReadLn(s2);
  if Length(s1) <> Length(s2) then
    begin
      WriteLn('No');
      Halt;
    end;
  for i := 1 to s1.Length do
    if Pos(s1[i], s2) = 0 then
      begin
        WriteLn('No');
        Halt;
      end
    else
      Delete(s2, Pos(s1[i], s2), 1);
  WriteLn('Yes');
end.
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32240 / 20880 / 8085
Регистрация: 22.10.2011
Сообщений: 36,118
Записей в блоге: 7
27.04.2018, 14:01 4
Лучший ответ Сообщение было отмечено Новичок как решение

Решение

JuriiMW, зачем же строку портить? Все проще, безо всяких сортировок:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var 
  s1, s2 : string;
  ch : byte;
  i : integer;
begin
  s1 := 'раз два три'; // Readln(s1);
  s2 := 'три две раз'; // Readln(s2);
  if length(s1) <> length(s2) then writeln('no')
  else
  begin
    ch := 0;
    for i := 1 to length(s1) do ch := ch xor byte(s1[i]) xor byte(s2[i]);
    if ch = 0 then writeln('yes') else writeln('no');
  end;
end.
1
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
28.04.2018, 22:50 5
Гениально и просто! Круто, не знал о таком приеме. А это ведь намного эффективнее чем сортировать строки(пусть даже быстро сортировать)
0
4951 / 2559 / 2310
Регистрация: 10.12.2014
Сообщений: 9,812
30.04.2018, 10:08 6
volvo, даём вашей программе следующие строки: "abe" и "xzd".
Логично, что ответ «No».
Смотрим, на работу программы:

Код
a — 97  — 01100001
b — 98  — 01100010
e — 101 — 01100101
x — 120 — 01111000
z — 122 — 01111010
d — 100 — 01100100

    00000000 {ch} — до цикла
xor 01100001 {a} — s1[1]
------------
    01100001
xor 01111000 {x} — s2[1]
------------
    00011001 {ch} — после 1 цикла
xor 01100010 {b} — s1[2]
------------
    01111011
xor 01111010 {z} — s2[2]
------------
    00000001 {ch} — после второго цикла
xor 01100101 {e} — s1[3]
------------
    01100100
xor 01100100 {d} — s2[3]
------------
    00000000 {ch} — после третьего цикла
В итоге, ваша программа говорит «yes»!
1
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32240 / 20880 / 8085
Регистрация: 22.10.2011
Сообщений: 36,118
Записей в блоге: 7
30.04.2018, 11:10 7
Интересно, что с xor-ом она говорит yes, а если заменить его на обычный +/-, то вроде подобных сбоев не наблюдается:
Pascal
1
2
3
var ch : integer;
// ...
for i := 1 to length(s1) do ch := ch + byte(s1[i]) - byte(s2[i]);
(проверял на FPC, надо бы еще с другими компиляторами проверить)
0
4951 / 2559 / 2310
Регистрация: 10.12.2014
Сообщений: 9,812
30.04.2018, 11:21 8
„— Это чё?
— КЦ.
— Надо снова проверять.
— Ну проверяй!“
/Кин-дза-дза/
0
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
30.04.2018, 11:49 9
JuriiMW прав. Не получится решать задачу за линейное время. Для кода из поста 7 есть например такой контртест: "ac", "bb".
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32240 / 20880 / 8085
Регистрация: 22.10.2011
Сообщений: 36,118
Записей в блоге: 7
01.05.2018, 11:09 10
Вот заучили как мантру "не получится", "задача за линейное время не решается" - вот и не получается. А я все-таки попробую. Объединяем методы:
Pascal
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
var 
  sum : integer;
  s1, s2 : string;
  ch : byte;
  i : integer;
begin
  s1 := 'раз два три';
  s2 := 'три две раз';
  //s1 := 'ac';
  //s2 := 'bb';
  //s1 := 'abe';
  //s2 := 'xzd';
  if length(s1) <> length(s2) then writeln('no')
  else
  begin
    ch := 0; sum := 0;
    for i := 1 to length(s1) do 
    begin
      ch := ch xor byte(s1[i]) xor byte(s2[i]);
      sum := sum + byte(s1[i]) - byte(s2[i]);
    end;
    writeln(ch, ' ', sum);
    if (ch = 0) and (sum = 0)
     then writeln('yes') else writeln('no');
  end;
end.
Попробуй найти контрпримеры... Но учти, у меня есть в запасе еще как минимум пара вариантов, которые не нарушат линейности времени поиска, поэтому чем больше будет контрпримеров - тем лучше Или можете продолжать наговаривать эту мантру о невозможности решения задачи, в это время находя очередной максимум в каждой строке матрицы.

Не по теме:

Напомнило:

- Голубчики, - сказал Фёдор Симеонович озабоченно, разобравшись в почерках. - Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.
- Мы сами знаем, что она не имеет решения, - сказал Хунта, немедленно ощетиниваясь. - Мы хотим знать, как её решать.
- Как-то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет? Бессмыслица какая-то…
- Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица - искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос…
(С) АБС, "Понедельник начинается в субботу"

Вот и мне неинтересно решать задачи, у которых уже есть решение, я хочу решить то, что сейчас решения не имеет.

0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
7060 / 4189 / 2727
Регистрация: 22.11.2013
Сообщений: 11,999
Записей в блоге: 1
01.05.2018, 11:51 11
volvo,
Соответственно вопрос: существует ли пара строк одинаковой длины p, q, для которых функции sxor(p)=sxor(q) и ssum(p)=ssum(q)?
Pascal
1
2
3
4
5
6
7
8
9
10
11
function SXor(const s: String): Byte;
var i: Integer;
begin
  Result:=0; for i:=1 to Length(s) do Result:=Result xor Byte(s[i]);
end;
 
function SSum(const s: String): LongWord;
var i: Integer;
begin
  Result:=0; for i:=1 to Length(s) do Inc(Result,Byte(s[i])-32);
end;
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
32240 / 20880 / 8085
Регистрация: 22.10.2011
Сообщений: 36,118
Записей в блоге: 7
01.05.2018, 12:11 12
Цитата Сообщение от bormant Посмотреть сообщение
существует ли пара строк одинаковой длины p, q, для которых функции sxor(p)=sxor(q) и ssum(p)=ssum(q)?
Нет. На этот вопрос я знаю ответ, "Да, такие строки существуют". Вопрос не в этом. Вопрос в том, "существует ли пара строк одинаковой длины p, q, содержащих несовпадающий набор символов, для которых ..." Вот на этот вопрос я ответа не знаю. Пока.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.05.2018, 12:11
Помогаю со студенческими работами здесь

Строки. Выясните, Можно ли из первой строки путём перстановки литер получить вторую
Добрый день. У меня проблема с такой программой: &quot;Пусть даны две строки str1 и str2. Выясните,...

Выяснить, можно ли из строки st1 сделать строку st2 путем перестановки символов
Ребят помогите пожалуста) Даны две строки st1 и st2. Выяснить можо ли из строки st1 сделать строку...

Ввести две строки. Вывести на экран можно ли, переставляя символы первой строки, получить вторую строку
Очень нужно решить задачу, чтоб экзамен поставили) Вот сама задача: Ввести две строки....

Определить, можно ли, переставляя символы в первой строке, получить вторую строку
Здравствуйте,дана такая задача:Даны две строки. Определить, можно ли, переставляя символы в первой...


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

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

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