Ancora puzzle smemorati

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Ancora puzzle smemorati

Messaggio da rand » 10 giu 2007, 15:37

Un'altro problemino che diventa non banale se vogliamo essere efficienti in spazio:

dato un array A[1]A[2]...A[n] e un intero K sovrascrivere l'array A con il suo shift
ciclico A[k]....A[n]A[1]...A[k-1] in tempo O(n) usando come memoria solo l'array A + una quantità costante e indipendente da n di registri.

Ciao.

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 10 giu 2007, 17:13

sia k<n
se m=(n,k)

Codice: Seleziona tutto

for(j=0; j<m; j++){
  for(b=a[i=0], q=j;i<n/m-1; i++){
    p=q;
    q=(p+k)%n;
    a[p]=a[q];
  }
  a[(j+n-k)%n]=b;
}
non l'ho ancora testato
solo un'idea
a occhio vi sembra ragionevole?

EDIT: ripensando a mente non funziona (lavora troppo)
Ultima modifica di SkZ il 10 giu 2007, 18:50, modificato 1 volta in totale.
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

mykelyk
Messaggi: 12
Iscritto il: 01 gen 1970, 01:00

Messaggio da mykelyk » 10 giu 2007, 18:27

Carino, se non capite ve lo spiego:

Codice: Seleziona tutto

// testconsole.cpp : definisce il punto di ingresso dell'applicazione console.
//

#include "stdafx.h"
#include <iostream> 

using namespace std;

typedef unsigned int uint;
typedef unsigned long long uint64;
//typedef int int;
typedef long long int64;

void multishift(uint end, int* a, uint k, uint n){
	uint start, i;
	start = end + k;
	i = start;
	int first = a[i];
	while((i %= n) != end){
		a[i] = a[(i + k) % n];
		i += k;
	}
	a[end] = first;
}
void shift(int* a, uint n, uint k){
	if(n && k){
		uint min = ~0;
		uint i = k;
		while(i != min){
			if(i < min) min = i;
			i = (i + k) % n;
		}
		for(i = 0; i <= min; i++)
			multishift(i, a, k, n);
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
#define n 200
#define k 7
	int a[n];
	for(uint i = 0; i < n; i++)
		a[i] = i + 1;

	shift(a, n, k);
	
	for(uint i = 0; i < n; i++)
		cout << a[i] <<endl;
	return 0;
}

Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand » 16 giu 2007, 15:41

Io avevo in mente questa soluzione. Si può vedere un qualunque shift ciclico come prodotto di 3 inversioni, dove un' inversione è una permutazione del tipo (a a+1 ... b-1 b) --> (b b-1 ... a+1 a). Poichè è facile effettuare un' inversione in loco e in tempo lineare anche lo shift ciclico viene così calcolato in loco e in tempo lineare.

Rispondi