Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничная новогодняя задачка / 25 сообщений из 47, страница 1 из 2
09.12.2015, 01:01
    #39123698
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Добрый день!

Предлагаю сообществу подумать над задачкой.
Типичный прогерИсходные данные: массив с числами типа Integer. Вам нужно написать функцию, которая на входе получит исходный массив, а на выходе вернет массив, в котором каждое значение получено путем произведения всех значений исходного массива с отличным от текущего индексом. Для ясности приведем пример.

Допустим, исходный массив имеет вид: [1, 7, 3, 4];
Тогда функция должна вернуть: [84, 12, 28, 21];
Расчет значений выглядит так: [7*3*4, 1*3*4, 1*7*4, 1*7*3];

Дополнительные условия:
1. Нельзя использовать деление.
2. Функция должна быть с наименьшими затратами памяти и времени выполнения.
Скажу честно что задачка не моя. Стырено из соц-сетей.
...
Рейтинг: 0 / 0
09.12.2015, 02:13
    #39123712
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
мы ее уже решили.
18335732
...
Рейтинг: 0 / 0
09.12.2015, 03:39
    #39123716
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
а Марк сопротивлялся когда я просил у него идеи в том обсуждении :p
...
Рейтинг: 0 / 0
09.12.2015, 13:03
    #39124047
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Не помню суть спора. Но кажется моё пожелание заключалось в том что формулировки надо писать
на русском языке.
...
Рейтинг: 0 / 0
09.12.2015, 13:45
    #39124092
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Не смотрел решения, рискну предположить, что нужно сформировать два вспомогательных массива, в одном будет произведение всех элементов 0.. i -1, в другом - i+1..N-1.
Результат получается путем скалярного их перемножения.
Вспомогательные массивы заполняются, естественно, перемножением предыдущего элемента на текущий (второй - в обратном порядке).
...
Рейтинг: 0 / 0
09.12.2015, 14:17
    #39124137
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
У меня была мысль умножать на 1/a[i] в хитром базисе. Как-бы в целых числах.
...
Рейтинг: 0 / 0
09.12.2015, 14:18
    #39124140
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
maytonумножать на 1/a[i]
как получить 1/a[i] без деления?
...
Рейтинг: 0 / 0
09.12.2015, 15:46
    #39124249
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Это загадка великая есть. Не знаю.
...
Рейтинг: 0 / 0
09.12.2015, 16:20
    #39124288
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Марк, да нет. Вы говорили о том что толку в решении задач Скиены с точки зрения развития в IT сфере нет ) Никаких споров у нас с вами не было) Наконец вы оторвались от ваших китайцев(вы по-моему ими занимались) и вернулись к Скиене :D

Соколинский Борис скалярного их перемножения

что вы имеете ввиду ?
...
Рейтинг: 0 / 0
09.12.2015, 16:39
    #39124308
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
SashaMercuryМарк, да нет. Вы говорили о том что толку в решении задач Скиены с точки зрения развития в IT сфере нет ) Никаких споров у нас с вами не было) Наконец вы оторвались от ваших китайцев(вы по-моему ими занимались) и вернулись к Скиене :D

Соколинский Борис скалярного их перемножения

что вы имеете ввиду ?

проще написать
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
type
  TOutputData=integer; //если нужно контролировать переполнение - заменить на что-то другое
  TOutputAr=array of TOuputData;

function CalcProd1(A: array of integer): TOutputAr;
var
  Xl, Xh:  TOutputAr;
  I, N: integer;
begin
  N:=Length(A);
  SetLength(Xl, N); SetLength(Xh, N);

  //заполнение вспомогательных массивов
  Xl[0]:=1;
  for i:=1 to N-1 do  Xl[i]:=Xl[i-1]*A[i-1];

  Xh[N-1]:=1;
  for i:=N-2 downto 0 do Xh[i]:=Xh[i+1]*A[i+1];

  //заполнение результата
  SetLength(Result, N);
  for i:=0 to N-1 do result[i]:=Xl[i]*Xh[i];
end;
...
Рейтинг: 0 / 0
09.12.2015, 16:51
    #39124317
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
SashaMercury, ох уж этот Майтон. Постит задачки из социальных сетей. Толи дело - академичные издания.... Мдя...
...
Рейтинг: 0 / 0
10.12.2015, 01:47
    #39124556
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Соколинский Борис проще написать
скалярного произведения в вашем коде нет )
...
Рейтинг: 0 / 0
10.12.2015, 08:31
    #39124595
Соколинский Борис
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
SashaMercuryскалярного произведения в вашем коде нет ) Ну да, неправильный термин.
Еще можно одним вспомогательным массивом обойтись.
Код: 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.
type
  TOutputData=integer; //если нужно контролировать переполнение - заменить на что-то другое
  TOutputAr=array of TOuputData;

function CalcProd1(A: array of integer): TOutputAr;
var
  Xh:  TOutputAr;
  I, N: integer;
  ProdL: TOutputData;
begin
  N:=Length(A);

  //заполнение вспомогательного массива
  SetLength(Xh, N);
  Xh[N-1]:=1;
  for i:=N-2 downto 0 do Xh[i]:=Xh[i+1]*A[i+1];

  //заполнение результата
  SetLength(Result, N);
  ProdL:=1;
  for i:=0 to N-1 do begin
    result[i]:=prodL*Xh[i];
    prodL:=ProdL*A[i];
  end;

end;
...
Рейтинг: 0 / 0
10.12.2015, 09:56
    #39124626
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Соколинский Борис, можно, всё верно
...
Рейтинг: 0 / 0
10.12.2015, 12:00
    #39124741
eNose
Участник
[не активирован]
[не одобрен]
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Типичный прогер1. Нельзя использовать деление.
2. Функция должна быть с наименьшими затратами памяти и времени выполнения. протеворичивые условия.

предлагаю использовать возведение в степень -1 и умножение.
...
Рейтинг: 0 / 0
10.12.2015, 12:44
    #39124826
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Там по условию задан массив целых. Как возводить целое в степень -1 с сохранением
условий задачи ХЗ.
...
Рейтинг: 0 / 0
10.12.2015, 15:50
    #39125085
eNose
Участник
[не активирован]
[не одобрен]
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
maytonТам по условию задан массив целых. Как возводить целое в степень -1 с сохранением
условий задачи ХЗ. в условии есть получить массив и вернуть массив.
а что там в черном ящике - ограничено только пунктами 1 и 2.
...
Рейтинг: 0 / 0
10.12.2015, 17:03
    #39125147
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
авторпредлагаю использовать возведение в степень -1 и умножение.
Предлагаю вместо 'привет' говорить 'здравствуйте'
...
Рейтинг: 0 / 0
11.12.2015, 14:07
    #39125853
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
mayton,

похоже, что можно решить эту задачу без дополнительной памяти )
...
Рейтинг: 0 / 0
11.12.2015, 14:57
    #39125888
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Чтобы не отвлекаться на эмуляцию арифметического сдвига вправо (SAR)
здесь для хранения целых чисел используется тип cardinal:

Код: sql
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.
type
  TMyArray= array of cardinal;

function Divide(x, y: cardinal): cardinal;
begin;
  while y and 1=0 do begin;
    x:=x shr 1;
    y:=y shr 1;
    end;
  Result:=1;
  while y<>1 do begin;
    Result:=Result*y;
    y:=y*y;
    end;
  Result:=Result*x;
  end;

procedure Calculate(a: TMyArray);
var
  x: cardinal;
  i, j, len: integer;
begin;
  len:=Length(a);
  x:=1; j:=-1;
  for i:=0 to len-1 do begin;
    if a[i]=0 then begin;
      if j>=0 then begin;
        j:=len;
        break;
        end;
      j:=i;
      end
    else x:=x*a[i];
    end;
  if j>=0 then begin;
    for i:=0 to len-1 do a[i]:=0;
    if j<len then a[j]:=x;
    end
  else for i:=0 to len-1 do a[i]:=Divide(x, a[i]);
  end;
...
Рейтинг: 0 / 0
12.12.2015, 12:28
    #39126336
Areostar
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
mayton,

А практический смысл!?
...
Рейтинг: 0 / 0
12.12.2015, 23:23
    #39126541
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Улучшенная версия:
Код: 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.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
type
  TMyArray= array of cardinal;

procedure Multiply(var x, e: cardinal; y: cardinal);
var
  m, d: cardinal;
begin;
  m:=1;
  d:=0;
  while y and m=0 do begin;
    m:=m+m;
    d:=d+1;
    end;
  x:=x*(y shr d);
  e:=e+d;
  end;

function Divide(x, e, y: cardinal): cardinal;
var
  m, d: cardinal;
begin;
  m:=1;
  d:=0;
  while y and m=0 do begin;
    m:=m+m;
    d:=d+1;
    end;
  y:=y shr d;
  e:=e-d;
  if e<8*SizeOf(x) then begin;
    while y<>1 do begin;
      x:=x*y;
      y:=y*y;
      end;
    Result:=x shl e;
    end
  else Result:=0;
  end;

procedure Calculate(a: TMyArray);
var
  x, e: cardinal;
  i, j, len: integer;
begin;
  len:=Length(a);
  x:=1; e:=0; j:=-1;
  for i:=0 to len-1 do begin;
    if a[i]=0 then begin;
      if j>=0 then begin;
        j:=len;
        break;
        end;
      j:=i;
      end
    else Multiply(x, e, a[i]);
    end;
  if j>=0 then begin;
    for i:=0 to len-1 do a[i]:=0;
    if j<len then a[j]:=Divide(x, e, 1);
    end
  else for i:=0 to len-1 do a[i]:=Divide(x, e, a[i]);
  end;

procedure TForm1.Button1Click(Sender: TObject);
var
  a: TMyArray;
begin;
  SetLength(a, 4);
  a[0]:=1;
  a[1]:=7;
  a[2]:=3;
  a[3]:=4;
  Memo1.Lines.Add(Format('%d %d %d %d', [a[1]*a[2]*a[3], a[0]*a[2]*a[3], a[0]*a[1]*a[3], a[0]*a[1]*a[2]]));
  Calculate(a);
  Memo1.Lines.Add(Format('%d %d %d %d', [a[0], a[1], a[2], a[3]]));
  end;
...
Рейтинг: 0 / 0
13.12.2015, 12:19
    #39126636
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Areostarmayton,

А практический смысл!?
Это очень хороший вопрос. По сабжу к каждому студенту который просит решить лабу
я могу обращаться с таким-же встречным. Но я надеюсь что в нашем скромном
форуме найдется место головоломкам без SR.

Не так ли?
...
Рейтинг: 0 / 0
15.12.2015, 20:35
    #39129146
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
mayton,

Есть интересный вариант задачи с похожим решением:

Длинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M.
Множители никак не упорядочены и не обязательно просты.
Известно, что B=A*х, где x - короткое.
Найти x.
...
Рейтинг: 0 / 0
15.12.2015, 20:45
    #39129151
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вторничная новогодняя задачка
Aleksandr Sharahov, если B=A*х то

x=B/A

Или я чет не так понял задание.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничная новогодняя задачка / 25 сообщений из 47, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]