powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Вторничная новогодняя задачка
25 сообщений из 47, страница 1 из 2
Вторничная новогодняя задачка
    #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
Вторничная новогодняя задачка
    #39123712
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
мы ее уже решили.
18335732
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39123716
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а Марк сопротивлялся когда я просил у него идеи в том обсуждении :p
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124047
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не помню суть спора. Но кажется моё пожелание заключалось в том что формулировки надо писать
на русском языке.
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124092
Соколинский Борис
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не смотрел решения, рискну предположить, что нужно сформировать два вспомогательных массива, в одном будет произведение всех элементов 0.. i -1, в другом - i+1..N-1.
Результат получается путем скалярного их перемножения.
Вспомогательные массивы заполняются, естественно, перемножением предыдущего элемента на текущий (второй - в обратном порядке).
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124137
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня была мысль умножать на 1/a[i] в хитром базисе. Как-бы в целых числах.
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124140
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonумножать на 1/a[i]
как получить 1/a[i] без деления?
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124249
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это загадка великая есть. Не знаю.
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124288
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Марк, да нет. Вы говорили о том что толку в решении задач Скиены с точки зрения развития в IT сфере нет ) Никаких споров у нас с вами не было) Наконец вы оторвались от ваших китайцев(вы по-моему ими занимались) и вернулись к Скиене :D

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

что вы имеете ввиду ?
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #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
Вторничная новогодняя задачка
    #39124317
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, ох уж этот Майтон. Постит задачки из социальных сетей. Толи дело - академичные издания.... Мдя...
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124556
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Соколинский Борис проще написать
скалярного произведения в вашем коде нет )
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #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
Вторничная новогодняя задачка
    #39124626
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Соколинский Борис, можно, всё верно
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #39124741
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[не активирован]
[не одобрен]
Типичный прогер1. Нельзя использовать деление.
2. Функция должна быть с наименьшими затратами памяти и времени выполнения. протеворичивые условия.

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

похоже, что можно решить эту задачу без дополнительной памяти )
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #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
Вторничная новогодняя задачка
    #39126336
Фотография Areostar
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

А практический смысл!?
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #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
Вторничная новогодняя задачка
    #39126636
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Areostarmayton,

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

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

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

Длинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M.
Множители никак не упорядочены и не обязательно просты.
Известно, что B=A*х, где x - короткое.
Найти x.
...
Рейтинг: 0 / 0
Вторничная новогодняя задачка
    #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]