Hollosi Information eXchange /HIX/
HIX CODER 1440
Copyright (C) HIX
2002-02-20
Új cikk beküldése (a cikk tartalma az író felelőssége)
Megrendelés Lemondás
1 Re: *** HIX CODER *** #1437 (mind)  47 sor     (cikkei)
2 Paradox psw. (mind)  40 sor     (cikkei)
3 Re: Rekurzio, backtrack (mind)  75 sor     (cikkei)
4 Grafkereso eljaras hiba C-ben (mind)  151 sor     (cikkei)
5 Midi programozas (mind)  13 sor     (cikkei)

+ - Re: *** HIX CODER *** #1437 (mind) VÁLASZ  Feladó: (cikkei)

Hi!

On Sun, 17 Feb 2002, HIX CODER wrote:

> =======================================================
> Felado :  [Romania]
> Temakor: Re: egy kis matek ( 20 sor )
> Idopont: Fri Feb 15 11:33:10 CET 2002 CODER #1437
> - - - - - - - - - - - - - - - - - - - - - - - - - - - -
> 
> magor wrote:
> 
> > algoritmust keresek 3 egysiban levo pontra kene kort rajzolni
> > kellene a sogar es a kozeppont
> 
> A kovetkezot otoltem ki: egy kor barmely hurjanak kozeppontjara
> meroleges a sug ar. Ugyhogy veszed 2 pont altal meghatarozott
> egyenest, megkeresed a felezojen a meroleges egyenletet, ugyanigy
>  2 masik ponttal ugyanezt
> teszed, kiszamolod a metszespontjukat, es ime! megvan a kozeppont.

A lenyeg magor, hogy _explicit_ ki lehet hozni a ket koordinatat. A ket
egyenletet le kell kodolni. Az elozo bekuldo ki is hozott valamit, nem
kovettem vegig.

> A sugar? Hmmm... Az nehez lehet... Talalj ki te valamit. En csak odaig

Hehe. Viccelsz? Ha mar megvan a kozeppont ket koordinataja, meg egy pont
koordinatati a koron, akkor egesz egyszeruen a ket pont altal alkotott
vektornak megnezed a hoasszat. Szamolsz egy tavolsagot.

d = r = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1))

> jutottam , hogy a kozeppont a koron levo barmely ponttol ugyanolyan
> tavolsagra van, de nem tudom mit kezdjek evvel. :)

Magyarul barmely pontra nezed a kozeppont tavolsagat, d = r.
:)

--

tocsa

 ---
| email:                        |
| homepage:  http://www.iit.bme.hu/~tocsa       |
 ---
+ - Paradox psw. (mind) VÁLASZ  Feladó: (cikkei)

This is a multi-part message in MIME format.

--Boundary_(ID_FzeW2CwKJ5cU7J7FlTyv8Q)
Content-type: text/plain; charset=iso-8859-2
Content-transfer-encoding: quoted-printable

Hello!

Tudom, hogy mar multkor (2-3honapja) megkerdeztem, de sajna az=F3ta =
meghalt a gepem es vele sok minden. Igy ujbol megkerdeznem valakitol:
Hogy lehet egy paradox tablanak futasi idoben a jelszot megadni =
Delphivel?
Koszonom: Peter

--Boundary_(ID_FzeW2CwKJ5cU7J7FlTyv8Q)
Content-type: text/html; charset=iso-8859-2
Content-transfer-encoding: quoted-printable

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content=3D"text/html; charset=3Diso-8859-2" =
http-equiv=3DContent-Type>
<META content=3D"MSHTML 5.00.2614.3401" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Hello!</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=3DArial size=3D2>Tudom, hogy mar multkor (2-3honapja) =
megkerdeztem,=20
de sajna az=F3ta meghalt a gepem es vele sok minden. Igy ujbol =
megkerdeznem=20
valakitol:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Hogy lehet egy paradox tablanak futasi =
idoben a=20
jelszot megadni Delphivel?</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Koszonom: =
Peter</FONT></DIV></BODY></HTML>

--Boundary_(ID_FzeW2CwKJ5cU7J7FlTyv8Q)--
+ - Re: Rekurzio, backtrack (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok!

Folytatom a backtrack-kel:

On 16 Feb 02, at 07:53, Ko'csi Zolta'n > wrote:

> A backtrack az egy problemat ugy old meg, hogy elindul es minden
> esetben, amikor egy dontest kell hozzon, feljegyzi, hogy ott milyen
> dontest hozott majd megy tovabb. Ha eljut egy olyan allapotba, mikor
> nyilvanvalo, hogy nincs megoldas az eddigi dontesekkel, akkor
> visszmegy es az utolso dontest megvaltoztatja.

Igy van. Annyit tennek hozza, hogy nem veletlen, hogy az eredeti 
kerdezo egyutt kerdezett ra a rekurziora es a backtrack-re, mivel a 
backtrack megvalositasa nagyon sokszor rekurzioval tortenik. 
Ugyanis ilyankor a korabbi dontesek feljegyzesevel nem kell tul 
sokat foglalkozni, a rekurzio folyaman majdnem minden 
adminisztralodik magatol a processzor stack-jen.

Vegyunk egy peldat: Ne a 8 kiralynot, arra mar szerintem tobbszor 
is kuldtem be programot en magam is, megvan az archivumban. A 
8 kiralyno sem bonyolult, de egy meg egyszerubbet talaltam ki: Ha 
van nalunk valahany db. 1, 5, illetve 10 Euros penzerme, akkor 
hogyan tudunk egy adott VAL osszeget ezekbol pontosan kifizetni 
maximum N db. erme felhasznalasaval? Illetve egyaltalan tudunk-
e? Es ha igen, hanyfelekeppen?

Az elso ket kerdesre persze backtrack nelkul is lehet viszonylag 
konnyen valaszolni, de most minket a backtrack erdekel, valamint 
az osszes lehetoseg kiszamitasa backtrack-kel egyszeru.

#define N 10    // max ennyi ermet hasznalhatunk fel
int ermek[N];   // ebben taroljuk, hogy milyen ermeket hasznalunk

// val-t kell felvaltanunk, van n1,n5,n10 db. 1,5,10 Euros ermenk
// i darab ermet hasznaltunk mar fel eddig. (Elso hivaskor
// i=0-at ad meg a hivo termeszetesen.)
void penzvaltas(int val, int n1, int n5, int n10, int i)
{
	if (val == 0) {
		// kesz vagyunk, sikerult felvaltani
		int j;
		for (j=0; j<i; j++)          // kiirjuk a talalt megoldast
			printf(" %d", ermek[j]);
		printf("\n");
		return;
	}
	if (i==N)
		return;   // sorry! Tul sok erme kellene!

	if (val > 10 && n10 > 0) {
		ermek[i]=10;	// probalkozunk egy 10-essel
		penzvaltas(val-10, n1, n5, n10-1, i+1);
	}
	// a 10-est beken hagyjuk (visszalepunk), es ...
	if (val > 5 && n5 > 0) {
		ermek[i]=5;	// megprobaljuk az 5-ost is
		penzvaltas(val-5, n1, n5-1, n10, i+1);
	}
	// az 5-ost is beken hagyjuk, es ...
	if (val > 1 && n1 > 0) {
		ermek[i]=1;	// vegul az 1-est probaljuk.
		penzvaltas(val-1, n1-1, n5, n10, i+1);
	}
}

Ez a rutin kiirja az osszes lehetseges megoldast, bar sajnos a 
megoldasok osszes permutaciojat is kiirja, amik vegulis nem mind 
kulonbozo megoldasok. Mindenesetre remelem, a peldabol jol 
latszik a backtrack lenyege. Remelem, az is latszik, hogy elsore 
fel sem tunik, hogy ez nem csak rekurzio, hanem backtrack is. Ez 
tipikus olyankor, amikor a backtrack rekurzioval van megoldva. Ez 
a szep a dologban :)

István
+ - Grafkereso eljaras hiba C-ben (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok. Ujra van egy nagyobbacska problemam.

   Egy feladatban arra van szuksegem, hogy valos uthalozatban keressem meg a
legoptimalisabb utat,vagyis  a legrovidebbet. Van is egy grafkereso
eljarasom, csak abban valami hiba van. Jol mukodik pl. olyan helysegek
eseteben amelyek "haromszog" vagy "kor" formaban es strukturaban
helyezkednek el, de nem mukodik jol, amikor a helysegek egy uton
helyezkednek el, egymas utan. Semmikeppen nem tudom megtalalni a hibat.
Leirom a forraskodot, hatha valaki meg tudna talalni a hibat. Nagyon
megkoszonnem.

   Miko Janos         Nagyvarad

#include <stdio.h>
#include <conio.h>
#include <string.h>

int inf=18000,c[30][30],d[30][30][30],dr[30],n,m,i,j,k,lg,vp;
char var[30][30],starth[30];

void inithalmaz(int s,int o,int k)
{
   d[s][o][1]=k;
   d[s][o][0]=2;
 }
void beteszhalmaz(int s,int o,int k,int p)
{  int i,j,l;

   j=d[k][o][0];
   i=d[s][o][0];
  if(p==1)
  {
   for(l=1;l<j;l++)
    d[s][o][i++]=d[k][o][l];
    d[s][o][0]=d[s][o][0]+l;
    }
    else
     { for (l=1;l<=n;l++)
 d[s][o][l]=0;
       for(l=1;l<=j;l++)
 d[s][o][l]=d[k][o][l];
 d[s][o][0]=j;
     }
 }

int vanahalmaz(int s,int o,int k)
{
 int i;
 for(i=1;i<=n;i++)
    if (d[s][o][i]==k) return (1);
 else return (0);
}

void olvas(void)
    {int i,j,t ;

    printf("Krem a varosok szamat");
    scanf("%d", &n);
    for(i=1;i<=n;i++)
      scanf("%s",&var[i]);
    for (i=1;i<=n;i++)
       for (j=1;j<=n;j++)
       {   c[i][j]=inf;
    c[i][i]=0;
  }
    for(i=1;i<=n-1;i++)
      for(j=i+1;j<=n;j++)
 {
   printf("Kerem a %s es a %s varosok kozti tavolsagot",var[i], var[j]);
   scanf("%d",&t);
   if (t!= 0)
       c[i][j]=c[j][i]=t;
 }
     printf("Kerem a kiindulo varos nevet");
     scanf("%s",&starth);
 for (i=1;i<=n;i++)
   {
     if (strcmp(starth,var[i])==0)
       vp=i;
   }

    }

void init(void)
{
   int i,j;
   for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
      if ((c[i][j]<18000) && (i!=j))  inithalmaz(i,j,i);
    else inithalmaz(i,j,0);

}
void ut(int i, int j)
{
  int k;
  if(i!=j)
    { for(k=1;k<=n;k++)
 if (vanahalmaz(i,j,k))
   { lg=lg+1;
     dr[lg]=k;
     ut(i,k);
     lg=lg-1;
   }
      }
    else
    { printf("\n");
      for(k=lg;k>=1;k--)
 printf("%s ",var[dr[k]]);
     }
}
void kiir()
{
 int i,j;
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  { printf("\n");
    if (c[i][j]==18000) printf("Nincs ut a %s tol a %s \n",var[i],var[j]);
 else
   { printf("A minimalis ut az %s varostol a %s varosig az
%d\n",var[i],var[j],c[i][j]);
    if (i!=j)
      {
       lg=1;
       dr[1]=j;
       ut(i,j);
       }
    }
  }
}
void main()
{olvas();
 init();
 for(k=1;k<=n;k++)
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
   if(c[i][j]>c[i][k]+c[k][j])
  { c[i][j]=c[i][k]+c[k][j];
    beteszhalmaz(i,j,k,0);
    }
   else
   if (c[i][j]==c[i][k]+c[k][j])
   beteszhalmaz(i,j,k,1);
  kiir();
getch();
}



_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
+ - Midi programozas (mind) VÁLASZ  Feladó: (cikkei)

Sziasztok!

   Olyasmi emberkenek a segitsegere lenne szuksegem, aki mar foglalkozott
   MIDI programozassal. A feladat az, hogy adott egy MIDI keyboard ami
   a hangkartya MIDI IN re van kotve, es ezen egyseg altal kuldott
   midi uzeneteket kellene feldolgoznom.  (Igazabol a komm. mikentje
   erdekelne).
   Foleg dokumentacio, url, newsgroup cimek, url-ek esnenek jol.
   Eseteleg nincs meg valakinek a Maximum Midi c. kivalo, de kb.
   49 USD-t kostalo konyv CDmellekleten levo forrasok? :)))

   udv, 
       Krisztian  )

AGYKONTROLL ALLAT AUTO AZSIA BUDAPEST CODER DOSZ FELVIDEK FILM FILOZOFIA FORUM GURU HANG HIPHOP HIRDETES HIRMONDO HIXDVD HUDOM HUNGARY JATEK KEP KONYHA KONYV KORNYESZ KUKKER KULTURA LINUX MAGELLAN MAHAL MOBIL MOKA MOZAIK NARANCS NARANCS1 NY NYELV OTTHON OTTHONKA PARA RANDI REJTVENY SCM SPORT SZABAD SZALON TANC TIPP TUDOMANY UK UTAZAS UTLEVEL VITA WEBMESTER WINDOWS