Mouvements minimum requis pour changer de position avec l’opération donnée

Étant donné deux entiers S et J et un tableau arr qui contient des éléments de 1 à N de façon non triée. La tâche consiste à trouver le nombre minimum de coups à déplacer qc élément à la Tth placer dans le tableau avec l’opération suivante :
Un seul mouvement consiste en ce qui suit

// Initially b[] = {1, 2, 3, ..., N}
// arr[] is input array
for (i = 1..n)
   temp[arr[i]] = b[i]
b = temp

Si ce n’est pas possible, imprimez -1 Au lieu.
Exemples:

Saisir: S = 2, T = 1, arr[] = {2, 3, 4, 1}
Production: 3
N est 4 (taille de arr[])
Coup 1 : b[] = {4, 1, 2, 3}
Coup 2 : b[] = {3, 4, 1, 2}
Coup 3 : b[] = {2, 3, 4, 1}
Saisir: S = 3, T = 4, arr[] = {1, 2, 3, 4}
Production: -1
N est 4 (taille de arr[])
Quel que soit le nombre de mouvements effectués, la permutation resterait la même.

Approcher: L’observation importante ici est que nous ne nous intéressons qu’à la position d’un seul élément, et non à l’ensemble du tableau. Ainsi, à chaque déplacement, nous déplaçons l’élément à la position S au poste arr[S]jusqu’à ce que nous arrivions Tth position.
Puisqu’il y a au plus N endroits distincts que nous pouvons atteindre, si nous n’atteignons pas J dans N se déplace, cela signifierait que nous ne pourrons jamais l’atteindre.
Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

int minimumMoves(int n, int a[], int s, int t)

{

    int i, x;

    x = s;

    for (i = 1; i <= n; i++) {

        if (x == t)

            break;

        x = a[x];

    }

    

    if (x == t)

        return i - 1;

    else

        return -1;

}

int main()

{

    int s = 2, t = 1, i;

    int a[] = {-1, 2, 3, 4, 1};

    int n = sizeof(a) / sizeof(a[0]);

    cout << minimumMoves(n, a, s, t);

}

Java

public class GFG{

static int minimumMoves(int n, int a[], int s, int t)

{

    int i, x;

    x = s;

    for (i = 1; i <= n; i++) {

        if (x == t)

            break;

        x = a[x];

    }

    

    if (x == t)

        return i - 1;

    else

        return -1;

}

    

    public static void main(String []args){

    int s = 2, t = 1, i;

    int a[] = {-1, 2, 3, 4, 1};

    int n = a.length ;

    System.out.println(minimumMoves(n, a, s, t)); 

    }

    

}

Python3

def minimumMoves(n, a, s, t):

    x = s

    for i in range(1, n+1): 

        

        if x == t:

            return i-1

        x = a[x]

     

    return -1

  

if __name__ == "__main__":

    s, t = 2, 1

    a = [-1, 2, 3, 4, 1]

    n = len(a)

    print(minimumMoves(n, a, s, t))

 

C#

using System;

public class GFG{

static int minimumMoves(int n, int []a, int s, int t)

{

    int i, x;

    x = s;

    for (i = 1; i <= n; i++) {

        if (x == t)

            break;

        x = a[x];

    }

    

    if (x == t)

        return i - 1;

    else

        return -1;

}

    

    public static void Main(){

    int s = 2, t = 1;

    int []a = {-1, 2, 3, 4, 1};

    int n = a.Length ;

    Console.WriteLine(minimumMoves(n, a, s, t));

    }

    

}

PHP

<?php

function minimumMoves($n, $a, $s, $t)

{

    $i; $x;

    $x = $s;

    for ($i = 1; $i <= $n; $i++) {

        if ($x == $t)

            break;

        $x = $a[$x];

    }

    

    if ($x == $t)

        return $i - 1;

    else

        return -1;

}

    $s = 2; $t = 1; $i;

    $a = array(-1, 2, 3, 4, 1);

    $n = count($a);

    echo minimumMoves($n, $a, $s, $t);

     

?>

Javascript

<script>

    

    

    

    function minimumMoves(n, a, s, t)

    {

        let i, x;

        x = s;

        for (i = 1; i <= n; i++) {

            if (x == t)

                break;

            x = a[x];

        }

        

        if (x == t)

            return i - 1;

        else

            return -1;

    }

    

    let s = 2, t = 1;

    let a = [-1, 2, 3, 4, 1];

    let n = a.length ;

    document.write(minimumMoves(n, a, s, t));

     

     

</script>

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Aller en haut