Zagadki algorytmiczne #3 – połowa sumy tablicy

Otrzymujesz listę liczb całkowitych. Twoim zadaniem jest zwrócenie jednego z jej elementów x, który spełnia warunek 2 * x = suma pozostałych elementów.

Masz zagwarantowane, że element x istnieje

Przykład:

Dla A = [1, 2, 3, 4, 5], wynikiem jest 5, bo 2 * 5 = 1 + 2 + 3 + 4.

  • Wejście: A int[]
    • 3 ≤ |A| ≤ 100, -1000 ≤ A[i] ≤ 1000
  • Wyjście int
    • jeden z elementów tablicy wejściowej

Priorytetem jest napisanie algorytmu zawierającego jak najmniejszą ilość znaków.

Sprawdź się, spróbuj sam rozwiązać!

Uwaga, poniżej przedstawionych jest kilka rozwiązań. Nie przewijaj jeśli sam chcesz pogłówkować.

Pierwsze przychodzące na myśl rozwiązanie

Algorytm jest bardzo prosty:

  1. W pierwszym kroku obliczamy w pętli sumę wszystkich elementów tablicy S.
  2. W drugim kroku i kolejnej pętli szukamy elementu spełniającego warunek a == (S – a) /2, bo 2 * a = S – a (S – a, czyli suma pozostałych elementów).

Algorytm po optymalizacji ilości znaków zawiera ich 79:

Najkrótsze rozwiązanie

Po chwili przypominamy sobie, że już w szkole podstawowej rozwiązywaliśmy równania z niewiadomą 🙂

Przeanalizujmy przypadek dla tablicy [1, 2, 3, 4, 5].

Element którego szukamy: x = 5
Suma wszystkich elementów: S = 1 + 2 + 3 + 4 + 5
Suma elementów z wykluczeniem x: a = 1 + 2 + 3 + 4

Układamy równanie:

S = a + x
x = a / 2, a zatem a = 2 * x

Wynika stąd, że:
S = a + x = 2 * x + x = 3 * x
S = 3 * x, dlatego x = S / 3

Wynikiem naszego algorytmu powinna być jedna trzecia sumy wszystkich elementów 🙂
Finalny algorytm został zoptymalizowany z 79 znaków do 51 i zawiera o jedną pętlę mniej:

Jak się podszkolić z bardziej poważnej algorytmiki?

Autor:

ISBN: 590-4-8070-0823-6

Format: , stron:

Data wydania:

Opis: PAKIET OBEJMUJE KSIĄŻKI: "Algorytmika praktyczna" Książka ta różni się od znanych na polskim rynku pozycji poświęconych algorytmice, dotyczy bowiem jej strony praktycznej. Taki sposób potraktowania tego działu informatyki wynika z coraz większego zainteresowania zarówno uczniów, jak i studentów udziałem w różnego rodzaju konkursach programistycznych. Czytelnik znaj

Cena: 62.50zł

Autor: Piotr Wróblewski

ISBN: 978-83-283-2132-8

Format: , stron:

Data wydania:

Opis: Wprowadzenie do algorytmiki Tylko niezbędna teoria Gotowe rozwiązania w C++ Oto kolejne wydanie sprawdzonej, cenionej przez programistów, wykładowców oraz studentów książki, będącej podstawowym podręcznikiem do nauki algorytmiki. Jej autor zapozna Cię z elementarnymi zagadnieniami z tej dziedziny oraz wyjaśni, skąd bierze się tak szybki postęp w

Cena: 49.00zł

 

To również może Cię zainteresować:

  • Zagadki algorytmiczne #2 – parser wyrażeń liczb rzymskichZagadki algorytmiczne #2 – parser wyrażeń liczb rzymskich Otrzymujesz jako tekst poprawne wyrażenie matematyczne, jednak zapisane liczbami rzymskimi. Twoim wyzwaniem jest zwrócić liczbę całkowitą będą wynikiem wyrażenia w systemie dziesiętnym. […]
  • Permutacje i zagadka z trójkątemPermutacje i zagadka z trójkątem Rozwiąż poniższą zagadkę: Rozwiązanie i trochę o permutacjach poniżej. Jednak zachęcam spróbować samodzielnie rozwiązać to zadanie. Rozwiązanie logiczne Warunkiem poprawności jest […]
  • 90-cio procentowe rabaty na ebooki!!!90-cio procentowe rabaty na ebooki!!! Równo o północy 3 listopada rusza zdecydowanie najlepsza promocja książek w tym roku - Ebookpoint.pl z okazji swoich piątych urodzin udostępnił ponad 8 tysięcy ebooków i audiobooków w […]
  • Testy PHP 7.0.0beta2 w WindowsTesty PHP 7.0.0beta2 w Windows Dziesiątego lipca 2015 została wydana wersja PHP 7.0.0 Beta1. Na dzień dzisiejszy dostępna jest już do pobrania Beta3 (6 sierpnia 2015), a najnowsze źródła i wersje skompilowane można […]
  • Zagadki algorytmiczne #1Zagadki algorytmiczne #1 Lubicie zagadki algorytmiczne? Jeśli tak, to zachęcam do wypróbowania https://codefights.com (jeśli jeszcze nie jest któremuś z Was znana ta platforma). Przypominam również o odbywających […]
  • PHP 7 został wydanyPHP 7 został wydany 3 grudnia 2015 została wydana oficjalna wersja PHP 7.0.0., w której wydajność w stosunku do PHP 5.6 została zwiększona nawet dwukrotnie. To, na co prawie każdy programista PHP czekał, to […]

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *