Enkel algoritm, men jag vet inte hur jag ska göra....

Permalänk

Enkel algoritm, men jag vet inte hur jag ska göra....

Hej på er!

Jag har ett litet problem. Jag har följande algoritm (som kastar om ordningen på elementen i en vektor på kvadratisk tid.):

Algorithm reverse(A):
Input: an array A storing n elements.
Output: the same array with the elements in reversed order.
for i = 1 to n-1
x = A[i]
for j = i downto 1
A[j] = A[j-1]
A[0] = x

Min uppgift är att hitta på en algoritm som gör samma sak, men på linjär tid. Beskriv din algoritm både i ord och i pseudokod.

Skulle vara väldigt tacksam för hjälp!

Permalänk
Medlem

Såhär kanske?

for (int i = 0; i < arraysize/2; i++) { temp = array[i]; array[i] = array[arraysize-i]; array[arraysize-i] = temp; }

Visa signatur

[Amd 2500+ @ 3200+] ¤ [Abit NF7] ¤ [1024 ddr @ 400 mHz] ¤ [Radeon 9600 pro] ¤ [Maxtor diamond max 160Gb] ¤ [Lain li PC 60]

http://forum.sweclockers.com/showthread.php?s=&postid=3916792...

Permalänk
Medlem

för o reversa en array så skulle jag göra nåt i stil med:

for (i = 0; i < A.length-1; i--) array2.append(array[i]);

Visa signatur

Awesome stuff can be found @ www.demonshalo.com
follow us on twitter: www.twitter.com/demonshalo_com

Permalänk
Hedersmedlem

För att förklara med ord och inte försökte vara häftig med någon kort kod(det skulle ju vara pseudokod).

Sätt pekare i början och slutet av arrayen. Swappa och rör pekarna inåt hela tiden tills de möts. Detta är i princip vad G4jm0r visade i kod.

Permalänk
Medlem

Hade visualstudio uppe, så jag tyckte det var enklare att skriva riktig kod istället för pseudo-kod.
Koden loopar igenom arrayen från båda sidor och swapar elementen med hjälp av en temp variabel. För att undvika tempvariabeln kan man skapa en ny array som man kopierar över värdena till i omvänd ordning, detta kräver dock mer minne eftersom man måste ha 2 arrayer allocerade, fördelen är väll att man slipper mellanlagra ett värde så det bör vara snabbare.

Visa signatur

[Amd 2500+ @ 3200+] ¤ [Abit NF7] ¤ [1024 ddr @ 400 mHz] ¤ [Radeon 9600 pro] ¤ [Maxtor diamond max 160Gb] ¤ [Lain li PC 60]

http://forum.sweclockers.com/showthread.php?s=&postid=3916792...

Permalänk
Medlem

Vet att detta inte riktigt har med frågan att göra, men jag har tråkigt (utvecklar burken startas om )

LINQ FTW:
Enumerable.Reverse<TSource> Method

char[] apple = { 'a', 'p', 'p', 'l', 'e' }; char[] reversed = apple.Reverse().ToArray(); foreach (char chr in reversed) { Console.Write(chr + " "); } Console.WriteLine(); /* This code produces the following output: e l p p a */

Edit: Lite överkurs, men om det är mycket data varför inte köra det parallelt?
Parallel LINQ (PLINQ)

var reverseOrder = customers .AsParallel() .AsOrdered() .Reverse();

Källa: How to: Control Ordering in a PLINQ Query

Visa signatur

CPU: i7 6700k + Fractal Design S24 GPU: ASUS GeForce GTX 1070 8GB DUAL OC RAM: Kingston 16GB 2133MHz CL13 MB: MSI GAMING M7 PSU: EVGA Supernova G2 850W, 80+ Gold SSD: Samsung SM951 256GB M.2 NVMe + Samsung EVO 850 250GB M.2 Chassi: Fractal Design S Skrämar: Acer XB270HU + 2x Dell U2412M
NAS: Synology DS415+ (4x WD RED 6 TB) Console: Xbox One