algorithm - testo - sequenze narrative e descrittive scuola primaria




Come determinare se una sequenza รจ bitonica? (4)

Una sequenza è bitonica se aumenta monotonicamente e poi diminuisce monotonicamente, o se può essere spostata circolarmente per aumentare monotonicamente e poi diminuire monotonicamente. Ad esempio le sequenze (1, 4, 6, 8, 3, -2), (9, 2, -4, -10, -5) e (1, 2, 3, 4) sono bitoniche, ma (1 , 3, 12, 4, 2, 10) non è bitonico.

Come può essere determinato se la sequenza data è bitonica?

Ho la seguente opinione. Possiamo camminare fino a n / 2 , dove n è la lunghezza dell'array, e controllare se

(a[i] < a[i + 1]) and (a[n - i - 1] < a[n-1 - (i + 1)])

È corretto?


Devono esserci esattamente due (o, a seconda di come la tua definizione si occupa della degenerazione, esattamente 0) transizioni tra salire e scendere. Non dimenticare di controllare la transizione tra [n] e [0].


Ecco un'implementazione efficiente e semplice in Java. Attraversa l'array solo una volta per determinare se l'array è bitonico o meno. Utilizza reversal variabile che conta il numero di inversioni di direzione della monotonicità nell'array (incluso l'avvolgimento circolare attorno).

L' trend variabile può avere tre valori:

  • 0 , se i valori sono uguali;
  • 1 , se l'array è in aumento monotonico;
  • -1 , se la matrice è monotonicamente decrescente.
public static boolean bitonic(int[] arr) {
  int reversal = 0;
  int len = arr.length;
  int trend = 0; // 0 means any, 1 means increasing, -1 means decreasing 
  for (int i= 0; i < len ; i++) {
    if(arr[i%len] < arr[(i+1)%len]){
      if (trend == 0) trend = 1;
      else if ( trend == -1) {
        reversal ++;
        trend = 1;
      }
    }
    else if(arr[i%len] > arr[(i+1)%len]){
      if (trend == 0) trend = -1;
      else if ( trend == 1) {
        reversal ++;
        trend = -1;
      }
    }
    if(reversal > 2) return false;
  }
  return true;
}

Una sequenza bitonica:

 /\
/  \
    \/

Non una sequenza bitonica:

 /\    
/  \  / (higher than start)
    \/

Ovviamente se la direzione cambia più di due volte non possiamo avere una sequenza bitonica.
Se la direzione cambia meno di due volte, dobbiamo avere una sequenza bitonica.

Se ci sono due cambiamenti nella direzione, potremmo avere una sequenza bitonica. Considera le due immagini ascii sopra. Chiaramente una sequenza con due cambiamenti di direzione corrisponderà a uno dei modelli (consentendo una riflessione). Quindi, impostiamo la direzione iniziale confrontando il primo e l'ultimo elemento. Poiché possono essere uguali, utilizziamo il primo elemento che non è uguale all'ultimo elemento.

Ecco un'implementazione in Java:

public static Boolean bitonic(int[] array) {
    if (array == null) return false;
    if (array.length < 4) return true;
    Boolean dir;// false is decreasing, true is increasing
    int pos = 0, switches = 0;
    while (pos < array.length) {
        if (array[pos] != array[array.length - 1])
            break;
        pos++;
    }
    if (pos == array.length) return true;
    //pos here is the first element that differs from the last
    dir = array[pos] > array[array.length - 1];
    while (pos < array.length - 1 && switches <= 2) {
        if ((array[pos + 1] != array[pos]) &&
           ((array[pos + 1] <= array[pos]) == dir)) {
            dir ^= true;
            switches++;
        }
        pos++;
    }
    return switches <= 2;
}

  • Attraversa in avanti la matrice, avvolgendoti quando colpisci la fine (codice sotto)
  • Contare il numero totale di punti di inflessione che si trovano, se num_inflection_points==2 quindi la matrice è bitonica.
  • Il tempo di esecuzione di questo dovrebbe essere O(n) .

-

Ecco un esempio funzionante in c ++:

bool is_bitonic(const vector<int>& v) {
  bool was_decreasing = v.back() > v.front();
  int num_inflections = 0;
  for (int i = 0; i < v.size() && num_inflections <= 2; i++) {
    bool is_decreasing = v[i] > v[(i+1)%v.size()];
    // Check if this element and next one are an inflection.
    if (was_decreasing != is_decreasing) {
      num_inflections++;
      was_decreasing = is_decreasing;
    }
  }
  return 2 == num_inflections;
}
  • Note, a seconda della tua implementazione:

Nota 1: Ecco l'idea di base per attraversare un array in modo circolare:

for (int i = ip_index; i < array_length; i++) {
   int index = (i + 1) % array_length;  // wraps around to beginning
   // Retrieve the value with
   DoSomethingWithValue(array[index];)
}

Nota 2: Potrebbe semplificare il codice per circolarmente length + 1 la length + 1 elemnts, che garantirà di trovare entrambi i punti di flesso.

Nota 3: Oppure, potrebbe semplificare il codice se si cerca sempre il primo punto di inflessione che aumenta fino a diminuire (prima di cercare altri punti di flesso). In questo modo, la scansione deve solo preoccuparsi di trovare esattamente un altro punto di inflessione con il capovolgimento opposto.

Nota 4: Come per l'esempio, non è possibile utilizzare N/2 , poiché il punto di flesso non si verifica necessariamente nel punto medio dell'array.





algorithm