Zagadki 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 się w grudniu X Mistrzostwach Wielkopolski w Programowaniu Zespołowym, do których zapisy zostaną otwarte w tym miesiącu.

Zadanie

Załóżmy, że każda tablica składa się z kilku pierścieni (warstw), które ponumerowane są rozpoczynając od 1 jako zewnętrznej warstwy, 2 jako kolejnej i tak dalej zmierzając do jej środka.

zadanie

Dla wskazanej liczby N zostaje zwrócona tablica o rozmiarze NxN.

Przykład:

Dla N = 1 wynikiem jest

Dla N = 2 wynikiem jest

Dla N = 3 wynikiem jest

Dla N = 4 wynikiem jest

  • Celem zadania jest napisanie algorytmu zawierającego jak najmniej znaków (nie licząc spacji i tabulacji).
  • Wejście: liczba całkowita N będąca rozmiarem tablicy, 1 ≤ N ≤ 100.
  • Wyjście: dwuwymiarowa tablica liczb całkowitych, [][]

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

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

Nauka algorytmiki:

Na dzień dzisiejszy (to jest 11.10.2015) trwa promocja w Helionie na zakup niektórych ebooków. Po wybraniu w koszyka opcji „Kupon rabatowy” i wpisaniu kodu: „HELIONPL„, wartość koszyka zostanie pomniejszona o 40%!

Ebooki związane z algorytmiką:

  1. Algorytmy. Almanach, cena po rabacie: 23,40 zł.
  2. Algorytmy bez tajemnic, cena po rabacie: 19,19 zł.
  3. Algorytmy, struktury danych i techniki programowania. Wydanie V, cena po rabacie: 23,40 zł.

A tu jeszcze jedna dobra książka drukowana:

  1. Algorytmika praktyczna

Kolejne wyzwanie

W chwili obecnej aktywne jest kolejne wyzwanie. Zadanie polega na napisanie parsera wyrażeń matematycznych liczb rzymskich. Dodam, że prowadzi osoba, która zaimplementowała algorytm w Javascript w zaledwie 152 znakach!

Moje rozwiązanie w Javie

Priorytetem w napisaniu algorytmu powinno być to, aby umieścić w nim jak najmniejszą ilość znaków. Dlatego o czystym kodzie można zapomnieć. Zadanie to można rozwiązywać na wiele sposobów. Sam wyzwanie ukończyłem na 31 miejscu z ilością znaków równą 153, zastosowawszy w przebiegu jedną pętlę:

Zwycięzcy wyzwania

Jak zobaczycie poniżej, rozwiązanie zawierające najmniejszą ilość znaków zostało napisanie w Pythonie.

 

Java, 116 znaków:

Zastosowano tu przebieg w dwóch pętlach.

C++,  136 znaków:

Tu widzimy nawet trzy pętle.

Python, 72 znaki:

Javascript, 100 znaków:

A zwycięzca w Javascript zastosował rekurencję.

Ciekawostka, najdłuższy algorytm (Java, 1301 znaków) 🙂

 

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

  • Zagadki algorytmiczne #3 – połowa sumy tablicyZagadki 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 […]
  • Raspberry PI 2, nauka podstaw Pythona 3Raspberry PI 2, nauka podstaw Pythona 3 W jednym z ostatnich wpisów zebrałem sobie źródła wiedzy do nauki Pythona, a w międzyczasie kupiłem Raspberry PI 2. Jedno z drugim jest mocno powiązane, ponieważ minikomputer standardowo […]
  • Tricki bitoweTricki bitowe W tym miejscu postaram się zebrać zbiór użytecznych operacji na bitach. Z biegiem czasu lista będzie aktualizowana. Zachęcam do przesyłania własnych propozycji! Znane i mniej znane […]
  • Wykonywanie kodu JavaScript w JavieWykonywanie kodu JavaScript w Javie Wraz z pojawieniem się Javy 8 został udostępniony nowy silnik JavaScriptowy dla JVM o nazwie Nashorn. Zastąpił on starszą implementację Rhino, dostępnego od Javy 6. JavaScriptowy silnik […]
  • jQuery Cluetip – opóźnienia żądań ajaxowychjQuery Cluetip – opóźnienia żądań ajaxowych W ostatnim czasie pracowałem nad modułem ewidencji czasu pracy w systemie kadrowo-płacowym. System intranetowy, ograniczona ilość użytkowników. Z tych, a nie innych względów na […]
  • PHP i podobieństwo dwóch wyrazówPHP i podobieństwo dwóch wyrazów Trafiłem ostatnio na ciekawą sytuację. Blisko dziewięć lat temu napisałem system dla zarządzania awizacjami kierowców w magazynach dla największego w Polsce producenta wody. System do dziś […]

Dodaj komentarz

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