Kategoria: programowanie / c


15 kwietnia 2012 (niedziela), 20:13:13

Programować każdy może (3)

Nie wiem czy jeszcze dziś potrafię, bo nie mam stosownego narzędzia - ale mam dowód, że kiedyś potrafiłem.

Napisałem to, ponieważ nie umiałem ułożyć układanki w pudełku, ale potrafiłem napisać program, który szukał rozwiązania.

 

Łamigłówka była elementem jakiejś fajnej gry przygodowej, którą A. zainstalowała na domowym iPadze, i której nie potrafiłem przejść, bo była właśnie ta łamigłówka. Programowanie zajęło mi z 8 godzin jak nic, przy czym dużo czasu kosztowało stworzenie środowiska do pisania w C (wyszło, że gcc na Linixie i vi jest nawłaściwsze), a dużo ponowne nauczenie się podstaw tego języka. Algorytm rekurencyjny był najmiejszym problemem.

Programowanie jest fajne!

 

#include 
#include 

#define DEBUG 2

#define NN 8
#define MM 6

int Lww = 0, Lwu =0;

struct Figura {
 int n;		// wielkosc w poziomie
 int m;		// wielkosc w pionie
 int F[NN][MM];	// wskaznik na tablice opisującą
 int EEi;		// wspolrzędna i punktu EE figury
 int PPi;		// położenie figury na planszy - współrzędna i punktu EE lub -1
 int PPj;		// jak wyżej dla drugiej współrzędnej
};

// #include "z2.h"

#define LICZBA_FIGUR 11

struct Figura FFF [LICZBA_FIGUR] = {
 { 1, 1, {		// #0 - pojedynczy kwadracik
   { 12 },
   },
 },

 { 3, 3, {		// #1 - odwrócone T 
  { 0, 0, 1 },		// uwaga: wiersze są pionami!
  { 1, 1, 1 }, 
  { 0, 0, 1 },
  },
 },

 { 3, 3, {		// #2 - krzyżyk
  { 0, 2, 0 },
  { 2, 2, 2 },
  { 0, 2, 0 },
  },
 },

 { 3, 3, {		// #3 takie M albo W - niebieskie schodki
   { 3, 3, 0 },
   { 0, 3, 3 },
   { 0, 0, 3 },
   },
 },

 { 2, 3, {		// #4 duże Gama - zielony, do górnego lewego rogu pasuje
   { 4, 4, 4 },
   { 4, 0, 0 },
   },
 },

 { 4, 2, {		// #5 takie Zet ale naciągnięte
   { 5, 0 },
   { 5, 5 },
   { 0, 5 },
   { 0, 5 },
   },
 },

 { 4, 2, {		// #6 T z przeciągniętym na prawo daszkiem
   { 6, 0 },
   { 6, 6 },
   { 6, 0 },
   { 6, 0 },
   },
 },

 { 3, 2, {		// #7 takie L ale żeby je wstawić w prawy dolny róg
   { 0, 7 },
   { 0, 7 },
   { 7, 7 },
   },
 },

 { 3, 3, {		// #8 - ??
   { 0, 8, 0 },
   { 8, 8, 0 },
   { 0, 8, 8 },
   },
 },

 { 1, 5, {		// #9 - pionowa pałka o dlugości 5 kratek
   { 9, 9, 9, 9, 9 },
   },
 },

 { 2, 3, {		// #10 - do wstawienia w prawy górny róg
   { 10,  0,  0 },
   { 10, 10, 10 },
   },
 },

};

void drukuj_tablice (int PP [NN][MM]);
void drukuj_figure (struct Figura F);


// najważniejsza i jedyna funkcja co kładze figurę na planszy i woła siebie dla nasztępnej figury

int wstaw_figure (int PPP[NN][MM], struct Figura FFF [LICZBA_FIGUR], int kk, int level) {
 int i, j, n, m, a, l;
 int Xi, Xj, Ei;
 int tmpEEi, tmpIIe;			// trudne zmienne wykorzystywane przy obróbce wciętych figur
 int PP[NN][MM];			// lokalna tablica z planszą
 struct Figura FF [LICZBA_FIGUR];	// lokalny zestaw figur wraz z ich stanem i położeniem

 Lww++;				// to jest statystyka dla ciekawych

 // Przekonany byłem, że w C może przenosić jako argumenty całe złożone struktury danyc...
 // ... to na pewno się da, ale ja nie wiem jak się to robi. A może to dało się w C++?
 // ... nie pamiętam, więc na głupka kopiuję nawet nie strncpy() ale for()

 for (j=0; j<MM; j++)		// naprawdę nie pamiętam, kiedy przekazuje się do funkcji...
   for (i=0; i<NN; i++)	// ... tablicę, a kiedy adres do tablicy
     PP[i][j] = PPP[i][j];	// ... wiec wolę skopiować aby mieć to lokalnie u siebie

 for (l=0; l<LICZBA_FIGUR; l++) {	// to też ma być lokalne a nie wiem czy jest
   FF[l].n = FFF[l].n;
   FF[l].m = FFF[l].m;
//  FF[l].F = FFF[l].F;		// tu kopiowany jest adres tych tablic z kształtem
   for (j=0; j<FFF[l].m; j++)	
     for (i=0; i<FFF[l].n; i++)	
       FF[l].F[i][j] = FFF[l].F[i][j];
   FF[l].EEi = FFF[l].EEi;
   FF[l].PPi = FFF[l].PPi;
   FF[l].PPj = FFF[l].PPj;
 }

 // początek analizy figur na planszy
 // czy da sie tą figure posadzić?

 // wyznacz współrzędne punktu X - a więc najwyżej położonego pustego punktu

 j=0; a=1;
 while ( a && j 1) {
   printf ("\n* * * * * * Wciśnij Enter * * * * *");
   getchar();
   system ("clear");	// czy nie ma jakiejś tańszej metody czyszczenia ekranu niż wołanie powłoki systemu?
 }

 if (DEBUG > 0) {
   printf ("\nPoziom: %i, figura: %i \n\nStan pola PP:", level, kk);
   drukuj_tablice (PP);

   printf ("\nTestowana figura: %i, rozmar: %i, %i Ei: %i\nKształt figury:", kk, FF[kk].n, FF[kk].m, FF[kk].EEi);
   drukuj_figure (FF[kk]);

   printf ("\nProba polożenia figury na Xi=%i Xj=%i", Xi, Xj);
 }

 if (a) {		// niemożliwe, aby nie było pustego punktu - poważnie?
   if (DEBUG > 0) {
     printf ("\n* ponoć wszystkie pola są zajęte? dziwne! Coś nie tak wieć wciśnij Enter!");
     getchar ();
   }
   return -2;		// znak, że błąd w danyc, sterowaniu, albo algorytmie
 }

 // sprawdzam, czy figura FF[kk] wlezie w obszar PP

 if (Xi + FF[kk].n - FF[kk].EEi > NN) {	// nie wlezie w obszaw pola PP
   if (DEBUG > 0) 
     printf ("\n- figura nie mieści sie w poziomie z prawej");
   return -17;
 }
 if (Xi - FF[kk].EEi < 0) {
   if (DEBUG > 0) 
     printf ("\n- figura nie mieści się z lewej");
   return -18;
 }
 if (Xj + FF[kk].m > MM) { 
   if (DEBUG > 0) 
     printf ("\n- figura mie mieści się pionie");
   return -19;
 }

 // sprawdzam, czy da się położyć figurę aby nie zawadzać o inne, już położone

 tmpEEi = FF[kk].EEi; a=1;		// tmpEj - bo pierwsza linia jest krótsza o blade znaki figury
 tmpIIe = 0;
 j = Xj; m = 0;			// przebieganie po drugim wymiarze
 while (a && m < FF[kk].m) {
   i = Xi - tmpIIe; n = tmpEEi;  
   while (a && n < FF[kk].n) {
     if (PP[i][j] && FF[kk].F[n][m]) {	// czy nakładają się pola z PP planszy i F figury
       a = 0; break;
     }
   i++; n++;
   }
   if (!a)
     break;
   tmpIIe = FF[kk].EEi;
   tmpEEi = 0;				// druga linia analizowana normalnie

   j++; m++;
 }

 if (!a) {				// nakładają się, więc koniec procedury
   if (DEBUG > 0) 
     printf ("\n- figura %i nakłada się przy i=%i j=%i dla n=%i m=%i", kk, i, j, n, m);
   return -27;
 }


 // posadz figure skoro sie da
 // - tzn zmiana planszy PP
 // - tzn zmiana tabeli figur FFF bo kk-figura ma zapisane współrzędne gdzie posadzona

 Lwu++;		// to jakaś statystyka dla ciekawych

 FF[kk].PPi = Xi; 	// ustaw wspolrzednne gdzie sie miesci ta figura - tj. wskaźnik używalności jej
 FF[kk].PPj = Xj;	// uwaga na te dane, bo w PPi nie uwzględniono korekty EEi

 // posadź figurę na planszy

 tmpEEi = FF[kk].EEi;			// tmpEj - bo pierwsza linia jest krótsza o blade znaki figury
 tmpIIe = 0;
 j = Xj; m = 0;			// przebieganie po drugim wymiarze
 while (m < FF[kk].m) {
   i = Xi - tmpIIe; n = tmpEEi;  
   while (n < FF[kk].n) {
     if (FF[kk].F[n][m]) 		// czy nakładają się pola z PP planszy i F figury
       PP[i][j] = FF[kk].F[n][m];	// numer figury znacznikiem, że pole zajęte tą figurą   
   i++; n++;
   }
   tmpIIe = FF[kk].EEi;
   tmpEEi = 0;				// druga linia analizowana normalnie
   j++; m++;
 }

 printf ("\n+ zmieściło się, więc położyłem figurę %i w Xi=%i Xj=%i\nNowy stan tablicy PP:", kk, Xi, Xj);
 drukuj_tablice (PP);

 // przeleć się po wszystkich figurach nie uzywanych probujac je wstawic
 // jeżeli nie ma już figur to sukces !

 l=0; a=1;
 while (a && l<LICZBA_FIGUR) {
   if (FF[l++].PPi == -1)
     a = 0;
 }

 if (a) {
   printf ("\n+ oto jest rozwiązanie ! TaTaM !!! * * * * * Wciśnij Enter!");
   getchar ();
   return 0;
 }

 for (l=0; l<LICZBA_FIGUR; l++) {
   // czy figura jest jeszcze nie używana
   if (FF[l].PPi == -1) {	// jeżeli nie używana to ją wstawiaj
     printf ("\n+ wywoluje dla figury %i kolejny poziom %i", l, level+1);
     wstaw_figure ((PP), (FF), l, level+1);
   }
 }

 printf ("\n- na tym poziomie (%i) wszystko wywołano już wszystko i wszystko wróciło", level);

}  

/*********************************************************************/


int main () {
 int i, j, k, l, n, m;
 int PP[NN][MM];

 // wyzeruj plansze PP na której się będzie pracować
 for (i=0; i<NN; i++)
   for (j=0; j<MM; j++)
     PP[i][j] = 0;

 // przygotuj tabele figur
 // - policz ile jest figur
 // - wyznacz punkty EE
 // - wyzeruj położenie

 for (k=0; k<LICZBA_FIGUR; k++) {
   FFF[k].PPi = FFF[k].PPj = -1;	// znacznik, że figura nie używana

   // tu jeszcze wyznaczam punkt EEi
   // wyjaśnienie - EEi to ile punktów pustych jest w pierwszym rzędzie od lewej
   FFF[k].EEi=0;
   for (i=0; i<FFF[k].n; i++)
     if (FFF[k].F[i][0]) {
       FFF[k].EEi = i;
       break;
     }

 } 

 // główny kod programu

 printf ("\nProgram do rozwiązywania łaigłówki. 2012 (c) Eniac Software\n");
 printf ("\nLiczba figur: %i", LICZBA_FIGUR);
 printf ("\nWydruk figur aby je sobie pooglądać");

 for (k=0; k<LICZBA_FIGUR; k++) {
   printf ("\nFigura nr %i ma wymiary n=%i m=%i i parametr Ei=%i", k, FFF[k].n, FFF[k].m, FFF[k].EEi);
   drukuj_figure (FFF[k]);
 }

 for (k=0; k<LICZBA_FIGUR; k++) {
   printf ("\n");
   wstaw_figure (PP, FFF, k, 0);
 }
 printf ("\nStatystyka - Wywołań: %i, Postawień: %i", Lww, Lwu);

return 0;
}


void drukuj_tablice (int PP [NN][MM]) {
 int i, j;

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf (" %1i", i); 
 printf (" |");    

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf ("--"); 
 printf ("-|");    

 for (j=0; j<MM; j++) {
   printf ("\n|");
   for (i=0; i<NN; i++)
     printf (" %1C", PP[i][j] ? '@' + PP[i][j] : '.');
   printf (" |");
 }

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf ("--"); 
 printf ("-|");    

 printf ("\n|"); 
 for (i=0; i<NN; i++) 
   printf (" %1i", i); 
 printf (" |");    

 printf ("\n");

}  


void drukuj_figure (struct Figura F) {
 int i, j;

 printf ("\n|");
 for (i=0; i<F.n; i++)
   printf ("--");
 printf ("-|");

 for (j=0; j<F.m; j++) {
   printf ("\n|");
   for (i=0; i<F.n; i++) {
     printf (" %1C", F.F[i][j] ? '@' + F.F[i][j] : '.');
   }
   printf (" |");
 }

 printf ("\n|");
 for (i=0; i<F.n; i++)
   printf ("--");
 printf ("-|");
}


Kategorie: zawodowe, _blog, programowanie, programowanie / c


Słowa kluczowe: programowanie, język c


Komentarze: (0)

Skomentuj notkę
30 grudnia 2004 (czwartek), 15:56:56

Liczba pi

  1. Liczba Π (π) to bardzo ładna liczba, choć używając fontu Verdana nie od razu to widać. W Times wygląda ona tak Π (π) a przez co bardziej uwidocznione jest piękno jej zaokrągleń.
  2. Kalkulator firmy Microsoft będący elementem Windows 2000 powiedział, że

    2 arc cos 0 = 3,1415926535897932384626433832795

    Nieźle, ale czy można mu wierzyć, skoro wykryto w nim poważne błędy przy prostym dzieleniu.

  3. Programować każdy może, więc zaintrygowany pięknem π postanowiłem sobie wyliczyć ile to ta liczba w zasadzie ma. W pamięci plątało się jakiś wzór na szereg skończony co to do π miał być zbieżny ale pamięć jest zawodna więc w materiałach źródłowych odnalazłem wzór Wallisa po czym zaimplementowałem go w Exel-a. Wyszło tragicznie, bo Exel kończy się na 65536 wierszach (65536 to też ładna liczba, zwłaszcza dla takich jak ja, ludzi 16-bitowych) a w 65 tysiącach przybliżeń liczba π wypada blado (można powiedzieć, że jest za okrągła). W każdym razie od góry miałem 3.18 a od dołu 3.09 więc...
  4. Skoro nie Exel to Word (kurcze, ale wyrafinowanych narzędzi programistycznych używam). Zapisałem takie oto makro w VBA
    Sub wzor_wallisa()
        Dim n As Long
        Dim p As Boolean
        Dim pi As Double
        Dim np As Long
        Dim nn As Long
        n = 1 : p = True : np = 2 : nn = 1
        pi = 2
        While n < 100000
              n = n + 1
              pi = pi * np / nn
              If p Then nn = nn + 2       ' krok parzysty
              If Not p Then np = np + 2   ' nieparzysty
              p = Not p
              Debug.Print n, pi
        Wend
    End Sub

    i już wiem, że iteracja #99999 daje przybliżenie od dołu 3,14157694550873 a iteracja #100000 przybliża od góry 3,14160836159235. Słabo! Z ciekawości podnoszę poprzeczkę do miliona iteracji i niech sobie mój noterek policzy.

    No i policzył. Milionowa iteracja to 3,14159422438652 czyli błąd jest już na 6 pozycji. Cieniarstwo! Może napisze ten program jakoś inaczej, w innym języku, bez użycia arytmetyki rzeczywistej (double) i szybciej dojdę do jakiegoś wyniku jaki inni mieli w XVII w. bez komputerów.

  5. Lepsze przybliżenie

    3,1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 592307816...

  6. Przemyślenie

    Czasem wydaje mi się, że żyjemy w epoce, w której wszystko już co można było wymyślić wymyślono. Kiedyś to się męczyli, liczyli π, odkrywali zasady dynamiki i prawa Maxwella a teraz? Czego się nie tknąć to wymyślone, zbadane, opisany, zastosowane a jeżeli chciałoby się poszukać czegoś nowego to jest to tak wyspecjalizowane, tajemne, że praktycznie graniczy gdzieś z magią.

  7. Ciekawe linki

    W zasadzie wystarczy jeden: http://pl.wikipedia.org/wiki/Liczba_pi bo od niego można iść dalej w ciekawe miejsca.

  8. Dopisek (31 grudnia 2017)

    Przepisałem sobie to w C aby uruchomić na jakimś on-linowym kompilatorze:

    int main() {
        double pi;
        long int n;
        int p;
        unsigned long int np, nn;
        n = 1 ; p = 1;
        np = 2; nn = 1;
        pi = 2;
        while (n < 10000) {
              n = n + 1;
              pi = pi * np / nn;
              
              if (p) 
                nn = nn + 2;  // krok parzysty
              if (!p) 
                np = np + 2;  // nieparzysty
              
              p = !p;
              printf ("\n%8d %f", n, pi);
        }
        return 0;
    }

    Ale coś mi nie poszło. Efekt dla 1000 kroków to 3.143164. Nie znam się na C. Już się nie znam.

    A kompilator jest tu: http://www.compileonline.com/compile_c_online.php

Kategorie: informatyka, _blog, programowanie / c, programowanie /vba, programowanie


Słowa kluczowe: liczba PI, matematyka, VBA, informatyka, wzór Wallisa


Komentarze: (8)

margaux, January 8, 2005 22:40 Skomentuj komentarz


Bardziej od liczby "PI" interesuje mnie liczba "FI". Jeśli posiadasz materiały na ten temat-jestem zainteresowana.

Plusia, October 30, 2006 20:43 Skomentuj komentarz


Jak chcesz informacje na temat liczby Fi to przeczytaj sobie Kod Leonarda daVinci :D Dokładnie strony 121-128 :D Przypominam, że liczba Fi wynosi 1,618 i jest równa m.in. ilorazowi liczby pszczół płci żeńskiej i pszczół płci męskiej (tzw trutni) w jakimkolwiek ulu na świecie ;)

anonim, October 31, 2006 09:16 Skomentuj komentarz


najważniejsze to sięgnąć po wiarygodne źródła :-)

marekm, January 4, 2005 22:35 Skomentuj komentarz


najwieksze przyblizenie uzyskałem przy pomocy tego algorytmu z ciągiem ale stosowałem arytemetykę typu "własna procedura obliczania w słupkach liczb zapisanych jako ciąg cyfr w pliku tekstowym". Sposob był niezly ale miałem wtedy tylko 21MB dysku twardego a poza systemem i pascalem musiały sie tam mieścić jeszcze trzy pliki z ciągami cyfr. Teraz mam trochę więcej miejsc na dysku więc może napiszę ten progam jeszcze raz...

pepegi, January 3, 2005 11:47 Skomentuj komentarz


ech. albo machina latające wymyślać, albo jako pierwszy przekroczyć na kołach 100 km/h...
szewo> chyba e^Pi, nie?

anonim, December 31, 2004 09:08 Skomentuj komentarz


pi ect są mi obce jak działania na Area 51 :P
a wpisuje się, bo
chciałabym życzyć Ci wszystkiego dobrego w Nowym Roku :)

krisper, December 31, 2004 00:02 Skomentuj komentarz


było im łatwiej? powiedz to Kopernikowi :-) odnośnie liczenia na piechotkę, to te wszystkie logarytmy, całki, różniczki nie wymyślono po to by gnębić biednych studentów na pierwszym roku, ale po to by łatwiej liczyc takie dziwne rzeczy. a szkoda, że np. na początku nauki o logarytmach nie mówi się ludziom, do czego to kiedyś było potrzebne, albo, że całkowanie to takie po troszę przewidywanie przyszłości. a wracając do tematu "czy im było łatwiej". mieli tak samo przechlapane jak my, tylko inaczej.

szewo.blox.pl, December 30, 2004 20:57 Skomentuj komentarz


Zagadki dwie:

1. Co jest większe: e^Pi czy Pi^e (bez kalkulatora, proszę, bo to proste).

2. Na który miejscu w rozwinięciu liczby Pi zaczyna się ciąg 111 zer.
Skomentuj notkę

Disclaimers :-) bo w stopce coś wyglądającego mądrze można napisać. Wszystkie powyższe notatki są moim © wymysłem i jako takie związane są ze mną. Ale są też materiały obce, które tu przechowuję lub cytuje ze względu na ich dobrą jakość, na inspiracje, bądź ilustracje prezentowanego lub omawianego tematu. Jeżeli coś narusza czyjeś prawa - proszę o sygnał abym mógł czym prędzej naprawić błąd i naruszeń zaniechać.