Fliping Ein Array von Ones und Nullen

Question

Ich habe ein Array A besteht aus einem Array ones und zeroes. In einem Vorgang kann ich ein Range 1 to i1<=i<=N und flip das Array und invert es wählen.
Ich musste den minimalen Betrieb dafür finden.
Für Ex:

A = 0010 

Im ersten Operation in Bereich von 1 bis 4 zunächst die Array wir drehen und es

A = 1011 

im Bereich von 1 bis 1 Im zweiten Betrieb invertieren ersten Flip wir das Array und Invertzucker

es

A = 0011 

in thrid Betrieb im Bereich von 1 bis 2 erste wir das Array drehen und invertieren

A = 1111 

Also drei Operationen sind erforderlich. Wie kann ich die Minumum Anzahl von Betriebs finden

My Approach: 

Fabrikate Neue Element als ein und

while(end>=0){ 

    if(A[end]==1){ end--;continue;} 

    int i=0; 

    if(A[0]==1) { 
    ans++; 
    A[0]=0; 
    } 
    i = 0; 
    int j = end; 

    while(j>=i){ 
     // Flip the Array and inverted it. 
    } 
    ans++; 
    end--; 

} 

Dies ist gierig Ansatz gehen und ich denke, es wird nicht funktionieren.

Answer 1

Schwer zu sagen, ob dies die optimale Lösung ist (obwohl es, wie es aussieht) dies wie folgt ich tun würde (C++):

int puzzle_flip_invert(int *a,int n) 
    { 
    int i1,m,N=n,i,j; char b; 
    // here print the input a[N] 

    // solve the puzzle 
    for (m=0;;m++) 
     { 
     // starting ones -> zeros 
     if (a[0]==1) 
      { 
      for (i1=0;(i1<n-1)&&(a[i1+1]==1);i1++); 
      if (i1==n-1) break; // solution found 
      } 
     // cut ending ones and then ending zeros -> ones 
     else for (i1=n-1;(i1>=0)&&(a[i1]==1);i1--,n--); 
     // flip and invert a[i] i=<0,i1> 
     for (i=0,j=i1;i<=j;i++,j--) 
      { 
      b=1-a[i]; a[i]=1-a[j]; a[j]=b; 
      } 
     // here print partial solution a[N] and used range <1,i1+1> 
     } 
    // here print the result m 
    return m; 
    } 

Nutzung:

int a[4]={0,0,1,0}; 
puzzle_flip_invert(a,4); 

Ausgang (sorry den Druckcode nicht enthalten, da er plattformabhängig ist):

0010 
1011 range: <1,4> 
0011 range: <1,1> 
1111 range: <1,2> 
-------------- 
Needed: 3 steps. 
-------------- 

[ 0.013 ms] 

Leitgedanke (teilweise basierend auf Paul Hankin Vorschlag) ist:

1. wenn Array mit denen beginnt

   dann überprüfen, wie viele von ihnen sind dort zusammen. Wenn der ganze String aufhört, findet man eine Lösung, wenn man sie nicht umdreht und invertiert, so dass der String mit Nullen beginnt. Dies ist wichtig, damit wir die End-Nullen später loswerden können.

2. wenn Array mit Nullen beginnt

   dann überprüfen, wie viele diejenigen am Ende sind und schneiden Sie die Array-Größe n von ihnen, da dieser Teil des Arrays ist bereits getan. dann klappen und invertieren den Rest. Dadurch werden so viele letzte Nullen aus dem ausgeschnittenen Teil konvertiert wie möglich.

3. goto # 1

[Notizen]

Wie ich bereits erwähnte ich weiß nicht, ob dieser Ansatz eine optimale Lösung. Dafür müsstest du einen Beweis machen, der nicht mein Ding ist, also würde ich es nicht einmal versuchen. Wie auch immer ich denke, dieser Punkt ist ein guter Anfang ...

Vorsicht vor die array Indizierung in C++ ist von 0 nicht von 1 !!! Die Ausdrucke werden inkrementiert, so dass die Bereiche Ihrer Ausgabe entsprechen.

einige weitere Beispiele:

010 
101 range: <1,3> 
001 range: <1,1> 
111 range: <1,2> 
-------------- 
Needed: 3 steps. 
-------------- 

00001111001101110 
10001001100001111 range: <1,17> 
00001001100001111 range: <1,1> 
11110011011111111 range: <1,13> 
00000011011111111 range: <1,4> 
10011111111111111 range: <1,9> 
00011111111111111 range: <1,1> 
11111111111111111 range: <1,3> 
-------------- 
Needed: 7 steps. 
--------------