VPF::Интересная задача. - Форум программистов

Pakshin A. S.

Дата 3.12.2004, 21:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

Дан массив a: array [1..9] of integer; Даны числа x1,x2... Массив а составлен примерно так:
х1, х2 ... х1, х1, х2 Т. е. есть парные жлементы. Определить число, которое не имеет пары. Оно будет, т.к. длина массива нечетная. Проверку делаем через один проход по массиву.
Надеюсь понятно изложил... smile

Предлагаем варианты (и решения и красивого условия)...

S.A.P.

Дата 3.12.2004, 21:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

По моему это где то уже было smile

Pakshin A. S.

Дата 3.12.2004, 21:37 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

Где?

S.A.P.

Дата 3.12.2004, 21:39 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

http://forum.vingrad.ru/index.php?showtopic=33728

Pakshin A. S.

Дата 3.12.2004, 21:44 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

Тама си... мне нужно на Pascal... Подсказка:

Код


for i:=1 to 9 do
 Один оператор

Zero

Дата 3.12.2004, 23:50 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Насколько я понял, то у тебя одномерный массив, который сосотоит, только из чисел x1 и x2, если так то легко: берёш, загоняеш первое число в буферную переменную, а начиная со второго в цикле проверяеш, если текущее число a[i] равно буферной переменной то буферный элемент есть результат, иначе буфер присвоит текущее a[i], и т.д.
Хотя возможно я тебя не так понял, потому что это было бы слишком легко, и врядли ты бы его задал... smile

S.A.P.

Дата 4.12.2004, 00:15 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Цитата(Zero @ 3.12.2004, 23:50)

Насколько я понял, то у тебя одномерный массив, который сосотоит, только из чисел x1 и x2

чисел может быть много, причем все, кроме одного встречаются в массиве 2 раза. Одно число не повторяется. Нужно его вычислить за один проход.

Zero

Дата 4.12.2004, 01:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Не думаю, что кто-нибудь сможет предложить что-нибудь проще smile

Код


Program pr;
var
   m:Set of byte;
   a:array[1..9] of integer;
   i:integer;
   c:byte;
begin
     for i:=1 to 9 do
       begin
         write('a[',i,']=');
         readln(a[i]);
       end;
     for i:=1 to 9 do
         if a[i] in m then m:=m-[a[i]]
         else m:=m+[a[i]];
     for c:=0 to 255 do
       if c in m then writeln('Число не имеющее пары=',c)
end.

Хотя, прога имеет недостаток, это диапазон заначений типа Byte, а не Integer (из-за исп. множественного типа)

S.A.P.

Дата 4.12.2004, 01:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Цитата(Zero @ 4.12.2004, 01:26)

Не думаю, что кто-нибудь сможет предложить что-нибудь проще

есть решение проще. И по условию цикл должен быть один.

cardinal

Дата 4.12.2004, 02:57 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: нет
Всего: 99

Zero, посмотри ссылку, которую Perchilla дал...

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

Zero

Дата 4.12.2004, 10:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Цитата(Perchilla @ 4.12.2004, 01:48)

есть решение проще. И по условию цикл должен быть один.

Ну напиши...
А цикл, у меня один, а вторые два не не входят в суть решения, 1-ый для ввода массива, а 3-ий для вывода, а само решение в одном цикле

Код


for i:=1 to 9 do
  if a[i] in m then m:=m-[a[i]]
  else m:=m+[a[i]];

Оставшийся в множестве элемент, и есть результат. smile

Цитата(cardinal @ 4.12.2004, 02:57)

Zero, посмотри ссылку, которую Perchilla дал...

Там написано на Си, а я в нём не рублю. smile

Но впринципе, здесь можно 1-ый и 2-ой циклы совместить, хотя тогда не будет красиво смотрется, а получится каша.

Это сообщение отредактировал(а) Zero - 4.12.2004, 10:56

S.A.P.

Дата 4.12.2004, 11:23 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Zero у тебя тут в виде множетства организовано, а число типа Integer, так что не катит.
Добавлено @ 11:24

Цитата(Zero @ 4.12.2004, 10:54)

Ну напиши...

напишу, если не будет больше вариантов.

Pakshin A. S.

Дата 4.12.2004, 13:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

Perchilla
Пишите! smile

Zero

Дата 4.12.2004, 16:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Цитата(Perchilla @ 4.12.2004, 11:23)

Zero у тебя тут в виде множетства организовано, а число типа Integer, так что не катит.

Да я же сказал, что единственный её недостаток, это то что используется тип байт, а во всём остальном она очень хорошо работает, а то что массив у меня написан типа Integer, это опечатка, надо типа byte

Код


a:array[1..9] of byte;

Perchilla, чем мы будем тут спорить, напиши сейчас лучше своё предложение и все вопросы будут закрыты, только раз уж ты сказал что существует более простой способ чем мои те две строчки то напиши именно так... Мне тоже было-бы интересно посмотреть на решение.

Это сообщение отредактировал(а) Zero - 4.12.2004, 16:10

S.A.P.

Дата 4.12.2004, 16:56 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Код


for i:=1 to 9 do
  m:=m XOR a[i];

вот и все

Парные элементы проинвертируются, а одинарный останется.

Pakshin A. S.

Дата 4.12.2004, 17:29 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

Правильно!!! smile

Zero

Дата 4.12.2004, 18:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Что-то я непонял: smile

Вот это-т код

Код


m:=m XOR a[i];

нужно записать за место этого

Код


if a[i] in m then m:=m-[a[i]]
  else m:=m+[a[i]];

который я писал, так что-ли???
Что-то у меня он не компилится... И кстати, что знаит побитовое исключающее Или двух выражений (я не понял что написано в справке) и почему, если пишеш

Код


var
  i:byte;
...
begin
i:=4 XOR 3
end.

в результате получается что они складываются???

cardinal

Дата 4.12.2004, 19:01 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: нет
Всего: 99

Zero, почитай тут:
http://borlpasc.narod.ru/inzik/glava6/sifpobi.htm

--------------------

Zero

Дата 4.12.2004, 19:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

cardinal, немог бы мелкую подсказку дать, а то я не понял по твоей ссылке, что делает XOR... Конечно раз ты знаеш что он делает, тебе понятно, а если не знаешь то по тому как там написано трудно её разобрать. smile

А в справке Паскаля, написано плохо smile

, т.к. нету примера по её использованию
Добавлено @ 19:57
чуть не забыл, а почему код не компилится???

cardinal

Дата 4.12.2004, 20:28 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: нет
Всего: 99

Код


XOR.¦...0...¦..1
------+------+----
..0....¦...0...¦..1
------+------+----
..1....¦...1...¦..0

Вот таблица... Из нее выходит: из разных значение (0 1 и 1 0) получается 1, а одинаковых (0 0 и 1 1) 0.

На примере двух байт получим:

01101010 (106)
xor
01101101 (109)
=
00000111 (7)

Попробуй сделать тоже самое в калькуляторе Винды.

Цитата(Zero @ 4.12.2004, 17:26)

в результате получается что они складываются???

А это только иногда получается smile

--------------------

S.A.P.

Дата 4.12.2004, 21:30 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Цитата(Zero @ 4.12.2004, 19:55)

чуть не забыл, а почему код не компилится???

объяви переменную m как integer. Вроде должно работать.

Zero

Дата 4.12.2004, 22:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Цитата(Perchilla @ 4.12.2004, 21:30)

объяви переменную m как integer. Вроде должно работать.

Если ты имеешь ввиду, в моём примере переменную m, объявить как integer, то сто пудов работать не будет, т.к. у меня

Код


m:Set of byte;

множество, а в него не может входить более 255 элементов, так что похоже твой код не работает...
А хотя наверно я что-то всё равно не так сделал, не мог бы ты прислать свой код полностью...
cardinal, спасибо смысл понял!!!

Pakshin A. S.

Дата 4.12.2004, 22:17 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

короче:

Код


var
 a:array [1..9] of integer;
 y: integer;
 i:integer;
begin
 <...>
 y:=a[1];
 for i:=2 to 9 do
  y:=y xor a[i];
 writeln('Число без пары -> ', y);
 <..>
end.

S.A.P.

Дата 4.12.2004, 22:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Цитата(Zero @ 4.12.2004, 22:13)

Если ты имеешь ввиду, в моём примере переменную m, объявить как integer, то сто пудов работать не будет, т.к. у меня

блин, да не в твоем примере, а в моем!!!! Твой пример я не знаю, почему не компилится. И не set of integer, а просто integer.

Добавлено @ 22:37
Только щас заметил, что Pakshin A. S. уже написал.

Это сообщение отредактировал(а) Perchilla - 4.12.2004, 22:39

Zero

Дата 4.12.2004, 22:47 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Спасибо за разяснение, ваши мысли понял!!!
Добавлено @ 22:50

Цитата

Твой пример я не знаю, почему не компилится.

Он не компилился по этому

Цитата

И не set of integer, а просто integer.

S.A.P.

Дата 4.12.2004, 22:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2664
Регистрация: 11.6.2004

Репутация: нет
Всего: 71

Pakshin A. S. а зачем так?

Код


y:=a[1];
for i:=2 to 9 do
  y:=y xor a[i];

когда можно так

Код


for i:=1 to 9 do
  y:=y xor a[i];

Просто я подумал, что если Y будет нулевой, то XOR с первым элементом будет равносилен присваиванию.

Pakshin A. S.

Дата 4.12.2004, 22:55 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

Вот этого я не помню... По-моему ты прав.

Dayana

Дата 5.12.2004, 19:23 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник Клуба
Сообщений: 352
Регистрация: 6.10.2002
Где: Тель-Авив

Репутация: нет
Всего: 4

У нас такие задачки на собеседовании при приеме на работу задают... smile

Леша

Дата 7.12.2004, 00:49 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 72
Регистрация: 7.11.2004
Где: Менск, Беларуская НР

Репутация: нет
Всего: 1

А тепер попробуем с Single'ом...

Zero

Дата 8.12.2004, 00:34 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Ладно, раз уж здесь больше никто ничего не предложил, то окончательно утвердим метод Perchilla:, как самый простой. smile

Код


Program pr;
var
   i,m,n:integer;
begin
     for i:=1 to 9 do
       begin
         write(i,'─oe числo>');
         readln(n);
         m:=m XOR n;
       end;
     writeln('Число не имеющее пары=',m)
end.

Это сообщение отредактировал(а) Zero - 8.12.2004, 00:35

Zero

Дата 21.10.2005, 10:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2169
Регистрация: 23.10.2004
Где: Россия, г. Рязань

Репутация: нет
Всего: 24

Цитата(Zero @ 8.12.2004, 01:34)

Ладно, раз уж здесь больше никто ничего не предложил, то окончательно утвердим метод Perchilla:, как самый простой.

НЕЧЕСТНО я в том году не знал, язык С++... А оказывается Перчилла от туда усё скотал.... smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »