Ordinare senza se

[orsoulx]

La scuola dei giochi, vista l'elevato numero di domande di iscrizione, ha sottoposto gli aspiranti al seguente test, apparentemente orientato verso l'informatica.
In quattro memorie (A, B, C e D) vengono scritti numeri razionali diversi non noti ai candidati. Questi possono manipolare le memorie, senza mai conoscerne i contenuti, utilizzando istruzioni elementari del tipo oXy dove:
o è un'operazione basica - somma, sottrazione, moltiplicazione, divisione o potenza;
X è il contenuto di una delle memorie, che sarà utilizzato come primo operando;
y, il secondo operando, può essere un numero razionale digitato oppure il contenuto di una delle memorie.
Il risultato andrà a sovrascrivere il contenuto di X.
Es. -B3 e +B(-3) sottraggono 3 al contenuto di B;
:CD scrive in C il quoziente dei contenuti di C e D;
*AA e ^A2 scrivono in A il quadrato di quel che contiene.
Il test è superato quando nelle memorie compaiono i quattro numeri iniziali disposti in ordine crescente.
Qual è il numero minimo di istruzioni che assicurano il superamento del test?
Le 5 operazioni non sono indispensabili; quante sono necessarie?
Ciao

[axpgn]

Forse ho trovato l'algoritmo … … spero …

$\text(-AB)$
$\text(*B2)$
$\text(+BA)$
$\text(*AA)$
$\text(^A(1/2))$
$\text(*BB)$
$\text(^B(1/2))$
$\text(+BA)$
$\text(*A2)$
$\text(-AB)$
$\text(*A(-1))$
$\text(*A(1/2))$
$\text(*B(1/2))$

Si ripete per $AC$, $AD$, $BC$, $BD$ e $CD$

S.E.&O.

Cordialmente, Alex

[orsoulx]

@Alex,

hai, forse, esagerato: l'impianto è buono, ma mi pare che, nel caso di numeri entrambi negativi, alla fine resti in B un positivo. Assomiglia a quel che i linguisti chiamano ipercorrettismo.

Ciao

[axpgn]

Il fatto è che non funziona proprio con i negativi … … altro che "ipercorrettismo"

Cordialmente, Alex

[Alemin1]

Ciao, premesso che ho guardato e studiato approfonditamente la soluzione di @axpgn in quanto l'obbiettivo mi sembrava impossibile senza se (quanto devo ancora imparare di matematica):

ho verificato il metodo di @axpgn considerando solo A e B
che scritto "algebricamente" risulta
$ A=(|A+B|-|A-B|)/2 $
$ B=(|A+B|+|A-B|)/2 $
togliendo i valori assoluti (giusto per capire come funzionano le due equazioni) ho appreso come facevano a selezionare il valore da assegnare alla variabile,
da qui sono giunto alla formula
$ A=(A+B-|A-B|)/2 $
$ B=(A+B+|A-B|)/2 $
che sembra funzionare,
quindi il procedimento dovrebbe essere:

-AB
*B2
+BA
*AA
^A(1/2)
+BA
*A2
-AB
*A(-1)
*A(1/2)
*B(1/2)

Si ripete per AC, AD, BC, BD e CD

è corretto?
in caso "a Cesare quel che è di Cesare e a axpgn quel che è di axpgn"

[axpgn]

Bravo!
Grande!

Cordialmente, Alex

[orsoulx]

Grazie Alemin ; grazie di cuore , non solo e non tanto per la risposta al quesito, ma particolarmente per il modo di porgerla.
Comunque superato, da Alex^2, il passaggio cruciale, mancano ancora le risposte alle due domande.
I 66 (dedotto dal procedimento) passi per completare l'ordinamento superano del 65% il numero di quelli che credo strettamente necessari.
Ciao

[orsoulx]

Visto il letargo generale mi rispondo, parzialmente, da solo.

I passi necessari per ordinare i contenuti in una coppia di memorie sono solo 8, ad esempio per $ AB $ un modo (giocato molto su $B$) è il seguente:
$-BA $
$:B2$
$+AB$
$*BB$
$^B0.5$
$-AB$
$+BB$
$+BA$
Un'ulteriore riduzione per l'ordinamento complessivo si ottiene osservando che, per la proprietà transitiva delle relazioni di ordine, basta ordinare 5 coppie. In tutto bastano quindi 40 operazioni elementari.
Per quando concerne il numero di operatori necessari: uno si può eliminare senza oneri, un secondo a patto di aumentare i passi necessari, ed infine ci si può ridurre ad usarne solo due grazie ad uno sporco trucco sull'interpretazione del testo.
D'altra parte siamo in sala giochi

Ciao

[axpgn]

Visto che ti rispondi da solo allora ti "approvo" io

Qual è "lo sporco trucco"?

Cordialmente, Alex

[Super Squirrel]

Un'ulteriore riduzione per l'ordinamento complessivo si ottiene osservando che, per la proprietà transitiva delle relazioni di ordine, basta ordinare 5 coppie.

Per esempio AB, CD, AC, BD, BC?

[axpgn]

Io penso piuttosto $AD, BC, AB, CD, BC$

[orsoulx]

@Super Squirrel; axpgn,
soluzioni entrambe valide, ve ne sono altre 10 possibili.
Alex: uno 'sporco trucco' che ha ben poco da spartire con il tuo orologio mal funzionante. Se leggi bene il testo vedrai che all'esaminando non viene mai richiesto di sapere di aver superato la prova prima della conferma della macchina.
Ciao
PS Per qualche ragione a me ignota il correttore ortografico accetta "all'esaminanda" ma non "all'esaminando".

[Super Squirrel]

Il ragionamento che ho fatto è il seguente... i primi 4 scambi hanno lo scopo di posizionare il minimo e il massimo rispettivamente in A e D, mentre l'ultimo di ordinare gli elementi centrali contenuti in B e C.
Dei 4 scambi iniziali, i primi 2 vanno a confrontare a due a due i quattro elementi, mentre gli altri 2 vanno a confrontare i minimi e i massimi dei suddetti scambi.