Despre parametrii primiți de gestionarii de evenimente rutate (RoutedEventArgs, MouseButtonEventArgs etc.)

Exemplu:

private void Handler(object sender, MouseButtonEventArgs e)
{
    // ce înseamnă aici: sender, e.Source și e.OriginalSource ?
}
  • sender – elementul care gestionează evenimentul (de care gestionarul de evenimente este atașat)
  • MouseButtonEventArgs moștenește de la RoutedEventArgs:
    • e.Source – elementul pentru care a pornit evenimentul în arborele vizual (fie de sus în jos, fie de jos în sus)
    • e.OriginalSource – elementul cel mai adânc determinat prin hit testing din interiorul celui pentru care a pornit evenimentul în arborele vizual

Dat fiind arborele vizual al sursei XAML următoare:

<StackPanel x:Name="sp" UIElement.PreviewMouseLeftButtonDown="Handler">
    <Button x:Name="btn1">butonul 1</Button>
    <Button x:Name="btn2">butonul 2</Button>
    <Button x:Name="btn3" Padding="5">
        <Rectangle Width="100" Height="100" Fill="Blue" x:Name="r"/>
    </Button>
</StackPanel>

și în codul din spate:

private void Handler(object sender, MouseButtonEventArgs e)
{
    // ce înseamnă aici: sender, e.Source și e.OriginalSource ?
}

Când se face clic cu butonul de maus stâng pe:

  • btn1: sender va fi sp, e.Source va fi btn1, e.OriginalSource va fi btn1
  • btn2: sender va fi sp, e.Source va fi btn2, e.OriginalSource va fi btn2
  • btn3: sender va fi sp, e.Source va fi btn3, e.OriginalSource va fi:
    • r dacă se face clic pe pătratul albastru
    • btn3 dacă se face clic pe spațiul din btn3 din jurul lui r

Am folosit evenimentul PreviewMouseLeftButtonDown în loc de Click deoarece Click este un eveniment specific butoanelor, și când se face clic pe pătratul albastru din btn3, e.OriginalSource este tot btn3 în cazul evenimentului Click. Nu am folosit nici evenimentul MouseLeftButtonDown deoarece este gestionat de clasa Button și nu ajunge la Rectangle. Notația cu UIElement. funcționează deoarece Button și Rectangle, ambele moștenesc de la UIElement și XAML oferă posibilitatea de a atașa un gestionar de evenimente la strămoșul controalelor vizate de respectivul eveniment cu această notație.

Documentația oficială este aici. Alte informații relevante aici.

Cum să depanezi probleme de legătură a datelor în WPF

Tradus din engleză de aici: https://spin.atomicobject.com/2013/12/11/wpf-data-binding-debug/.

Legătura datelor stabilește o conexiune între interfața grafică a aplicației și logica afacerii. Când funcționează, este un lucru minunat. Nu mai trebuie să scrii cod care actualizează interfața ta grafică sau să pasezi valori în jos către logica afacerii. Când nu mai funcționează, poate fi frustrant să afli ce a mers prost. În această postare, îți voi da câteva sfaturi despre cum poți depana legăturile tale de date în WPF.

1. Adaugă urmărirea în fereastra Output

Aici este un simplu TextBlock care are un context de date lipsă. În această situație, nu vei obține nicio eroare în fereastra de ieșire a Visual Studio.

<Window x:Class="WpfApplication1.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="MainWindow" Height="350" Width="525">
    <Grid>
        <TextBlock Text="{Binding ThereIsNoDataContext}"/>
    </Grid>
</Window>

Pentru a activa urmărirea, am adăugat un nou spațiu de nume XML pentru a include spațiul de nume System.Diagnostics. Poți de asemenea seta nivelul de urmărire la High, Medium, Low sau None. Acum haide să adăugăm ceva urmărire la fereastra de ieșire pentru a vedea ce este greșit cu legătura datelor.

<Window x:Class="WpfApplication1.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:diag="clr-namespace:System.Diagnostics;assembly=WindowsBase"
        Title="MainWindow" Height="350" Width="525">
    <Grid>
        <TextBlock Text="{Binding ThereIsNoDataContext, 
            diag:PresentationTraceSources.TraceLevel=High}"/>
    </Grid>
</Window>

Acum fereastra de ieșire va conține următoarele informații ajutătoare:

System.Windows.Data Warning: 71 : BindingExpression (hash=38600745): DataContext is null

2. Atașează un convertor de valoare pentru a rupe execuția intrând în depanator

Când nu vezi nimic afișat în interfața ta grafică, este greu să spui dacă legătura datelor este cea care cauzează problema ta sau este o problemă cu așezarea vizuală a controlului. Poți elimina legătura datelor ca problema în cauză prin adăugarea unui convertor de valoare și să rupi execuția intrând în depanator. Dacă valoarea este cea așteptată, atunci legătura datelor nu este o problemă a ta.

Iată un simplu convertor de valoare care rupe execuția intrând în depanator.

using System;
using System.Diagnostics;
using System.Globalization;
using System.Windows.Data;
 
namespace WpfApplication1
{
    public class DebugDataBindingConverter : IValueConverter
    {
        public object Convert(object value, Type targetType,
            object parameter, CultureInfo culture)
        {
            Debugger.Break();
            return value;
        }
 
        public object ConvertBack(object value, Type targetType,
            object parameter, CultureInfo culture)
        {
            Debugger.Break();
            return value;
        }
    }
}

Pentru a folosi convertorul de valoare, faceți referire la spațiul de nume al asamblajului care conține convertorul și adaugă o instanță a lui la resursele ferestrei tale. Acum adaugă convertorul la legătura de date problematică a ta.

<Window x:Class="WpfApplication1.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        xmlns:local="clr-namespace:WpfApplication1"
        Title="MainWindow" Height="350" Width="525">
    <Grid Name="root">
        <Grid.Resources>
            <local:DebugDataBindingConverter x:Key="DebugBinding"/>
        </Grid.Resources>
        <TextBlock Text="{Binding ActualWidth, ElementName=root, 
            Converter={StaticResource DebugBinding}}"/>
    </Grid>
</Window>

3. Află instantaneu că ai o problemă de legătură a datelor

Decât dacă verifici constant fiecare element de interfață cu utilizatorul și monitorizezi fereastra de ieșire pentru erori de legătură a datelor, nu vei ști întotdeauna când ai o problemă de legătură a datelor. O excepție nu este aruncată când legătura datelor se strică, deci gestionarii de excepții globali nu sunt folositori.

Nu ar fi frumos dacă ai intra în depanator exact când ai o eroare de legătură a datelor? Adăugând propria noastră implementare a unui TraceListener care intră în depanator, vom fi notificați data viitoare când primim o eroare de legătură a datelor. Am adăugat de asemenea implicitul ConsoleTraceListener pe lângă noul nostru DebugTraceListener, astfel încât exemplele noastre anterioare de urmărire a ieșirii să nu fie stricate.

public partial class App : Application
{
    protected override void OnStartup(StartupEventArgs e)
    {
        PresentationTraceSources.Refresh();
        PresentationTraceSources.DataBindingSource.Listeners.Add(new ConsoleTraceListener());
        PresentationTraceSources.DataBindingSource.Listeners.Add(new DebugTraceListener());
        PresentationTraceSources.DataBindingSource.Switch.Level = SourceLevels.Warning | SourceLevels.Error;
        base.OnStartup(e);
    }
}
 
public class DebugTraceListener : TraceListener
{
    public override void Write(string message)
    {
    }
 
    public override void WriteLine(string message)
    {
        Debugger.Break();
    }
}

Cu aceste sfaturi, ar trebui să ai o experiență mai pozitivă cu legăturile datelor. Te rog să împărtășești în comentarii orice sfat de depanare în plus pe care l-ai putea avea.

Ce să faci când FrameworkElement.GetTemplateChild(string) întoarce null?

Dacă metoda GetTemplateChild aparent nu funcționează, încearcă să faci un constructor static pentru clasa elementului asupra căruia se aplică respectivul ControlTemplate:

De exemplu, dacă clasa se numește AudioFileSelector, acest cod va face ca GetTemplateChild să nu mai întoarcă null mereu.

static AudioFileSelector()
{
    DefaultStyleKeyProperty.OverrideMetadata(typeof(AudioFileSelector),
        new FrameworkPropertyMetadata(typeof(AudioFileSelector)));
}

Apoi, aproape la fel ca atunci când ai un UserControl cu elemente în conținutul lui cu atributul Name sau x:Name setat și le folosești direct specificându-le numele în fișierul cu extensia .xaml.cs, acum trebuie să declari la nivelul clasei, de obicei în același fișier .xaml.cs, câteva câmpuri (field-uri), câte unul pentru fiecare element cu nume din interiorul Template-ului pe care dorești să le folosești, chiar și doar pentru a gestiona anumite evenimente ale lor:

internal Button MyButton1, MyTextBox1;

și pui o suprascriere (override) la metoda OnApplyTemplate asftel:

public override void OnApplyTemplate()
{
    base.OnApplyTemplate();
   
    MyButton1 = (Button)GetTemplateChild("MyButton1");
    MyTextBox1 = (TextBox)GetTemplateChild("MyTextBox1");

    // eventual se atașează aici câteva handlere la evenimente ale MyButton1, MyTextBox1 etc.
}

apoi în interiorul clasei, oriunde este nevoie de aceste elemente ale ControlTemplate-ului se apelează:

ApplyTemplate();

în cazul în care acest apel întoarce true, se pot imediat apoi folosi câmpurile MyButton1, MyTextBox1 etc.

Apelul la ApplyTemplate apelează indirect OnApplyTemplate. El este necesar mai ales când este nevoie de un subelement înainte ca evenimentul Loaded al elementului asupra căruia se aplică ControlTemplate-ul să fie apelat.

Tutorial Xamarin – Hello World în 10 minute

Tradus de aici: https://dotnet.microsoft.com/learn/xamarin/hello-world-tutorial/intro.

Introducere

Scop

Configurează-ți mediul de dezvoltare și construiește prima ta aplicație pentru Android și iOS.

Cerințe preliminare

Niciuna.

Timp de completare

10 minute + timp de descărcare/instalare

Scenariu

O aplicație mobilă pentru Android și iOS care afișează un mesaj „Hello World”.

Descarcă și instalează

Descarcă și instalează Visual Studio 2019.

În timpul instalării, selectează cadrul de lucru Mobile development with .NET.

Ai deja Visual Studio?

Dacă ai deja Visual Studio 2019, poți adăuga acest cadru de lucru Mobile development with .NET:

  • Apasă tasta Windows, tastează Visual Studio Installer, și apasă Enter
  • Dacă ești întrebat, permite programului de instalare să se actualizeze
  • Găsește-ți instalarea Visual Studio 2019 și selectează More -> Modify
  • Selectează Mobile development with .NET și fă clic pe Modify

Configurează un dispozitiv sau emulator Android

După instalarea Visual Studio, configurează un dispozitiv fizic Android sau creează un emulator Android.

Dacă dorești, poți de asemenea împerechea cu Mac pentru dezvoltare Xamarin.iOS.

Prezentare video

Creează-ți aplicația

Creează o nouă aplicație Xamarin:

  1. Deschide Visual Studio 2019
  2. Selectează Create a new project
  3. Selectează Mobile din meniul drop-down Project type
  4. Selectează șablonul Mobile App (Xamarin.Forms) și clic pe Next
  5. Introdu AwesomeApp ca nume de proiect și clic Next
  6. Selectează șablonul Blank, asigură-te că Android și iOS sunt selectate, și clic pe OK

Restaurează pachetele NuGet

NuGet este un gestionar de pachete care va aduce dependențele noii tale aplicații.

Procesul de restaurare a pachetelor va începe automat. Așteaptă până când mesajul Restore completed apare în bara de stare în partea de jos a ecranului.

Execută-ți aplicația

Din meniu, selectează Debug -> Start Debugging.

Aplicația ta va construi apoi se va lansa pe emulatorul Android și se va executa.

Felicitări, ți-ai construit și executat prima ta aplicație mobilă .NET!

Editează-ți codul

Acum vei adăuga un buton la interfața grafică, împreună cu un eveniment de clic care va crește și afișa o numărătoare.

Oprește depanarea

Din meniu, selectează Debug -> Stop Debugging.

Adaugă un buton

Deschide MainPage.xaml și adaugă următorul cod sub <Label ... />:

<Button Text="Click Me" Clicked="Handle_Clicked" />

Adaugă un gestionar de eveniment

Deschide MainPage.xaml.cs și adaugă următorul cod înăuntrul clasei:

int count = 0;
void Handle_Clicked(object sender, System.EventArgs e)
{
    count++;
    ((Button)sender).Text = $"You clicked {count} times.";
}

Rulează aplicația

Din meniu, selectează Debug -> Start Debugging.

Când aplicația ta se pornește, apasă pe buton. Numărul de clicuri va fi afișat în interiorul butonului.

Prezentare video

Pașii următori

Felicitări, ți-ai construit și executat prima ta aplicație Xamarin cu sprijinul .NET!

Continuă să înveți

Acum că știi baza, continuă să construiești prima ta aplicație Xamarin cu pornirile rapide Xamarin.Forms.

[C++, programare dinamică] Problema înmulțirii optime a matricelor

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Se dau N matrice, considerate cu elemente numere reale, identificate printr-un vector de dimensiuni D. Astfel, matricea 1 ≤ i ≤ N are dimensiunea (D[i – 1], D[i]). Se cere găsirea numărului minim de înmulțiri scalare necesare pentru calcularea produsului celor N matrice.

Fișierul de intrare inmopt.in conține pe prima linie numărul N al matricelor, iar pe linia următoare N + 1 valori ce reprezintă vectorul de dimensiuni. Numărul minim de înmulțiri scalare se va afișa în fișierul inmopt.out.

Exemplu:

inmopt.ininmopt.out
3
4 3 2 5
64

Explicație: notăm cele trei matrice cu A, B și C. Numărul minim de înmulțiri scalare necesare se obține înmulțind matricele astfel: (A∙B)∙C. Daă am folosi parantezarea A∙(B∙C), am efectua 90 de înmulțiri.


Precizăm în primul rând că înmulțirea matricelor este asociativă, deci putem să parantezăm înmulțirea matricelor în orice mod valid fără a afecta rezultatul final.

În al doilea rând, numărul de înmulțiri scalare necesare pentru a înmulți două matrice de dimensiuni (x, y) și (y, z) este egal cu x∙y∙z.


Vom încerca să exprimăm recursiv problema. Notăm matricele date cu A1, A2, …, AN. Să presupunem că știm un k între 1 și N astfel încât parantezarea (A1∙A2∙…∙Ak)∙(Ak+1∙…∙AN) să fie o parte a soluției optime. Atunci, pentru a obține soluția optimă, trebuie să știm cum putem paranteza optim înmulțirile A1∙A2∙…∙Ak și Ak+1∙…∙AN.

Pentru a putea exprima matematic acest lucru, fie M[i][j] = numărul minim de înmulțiri scalare necesare înmulțirii secvenței de matrice [i, j]. Dacă știm calcula matricea M, atunci răspunsul problemei va fi M[1][N].


Se disting următoarele cazuri:

  1. Dacă avem o singură matrice, atunci nu trebuie efectuată nicio înmulțire scalară. Acesta este cazul de bază al recurenței, deci M[i][i] = 0 pentru orice 1 ≤ i ≤ N.
  2. Pentru aflarea numărului minim de înmulțiri scalare necesare pentru înmulțirea unei secvențe de matrice [i, j], 1 ≤ i < j N este necesar să știm poziția i ≤ k < j în care vom „împărți” secvența [i, j] în două secvențe parantezate separat [i, k] și [k + 1, j]. Dimensiunea matricei rezultate din înmulțirea matricelor din secvența [i, k] va fi dat de (D[i – 1], D[k]), iar dimensiunea celei rezultate din înmulțirea matricelor din secvența [k + 1, j] va fi dată de (D[k], D[j]). Avem așadar:

(n.e. Se adună la nr. de înmulțiri scalare optim pentru Ai * Ak, numărul de înmulțiri scalare optim pentru Ak+1 * Aj, și apoi se adaugă produsul celor 3 elemente ale D.)


Timpul de execuție al algoritmului este O(N3), deoarece pentru fiecare dintre cele O(N2) secvențe efectuăm o parcurgere în timp O(N) pentru a găsi k care verifică minimul de mai sus. Memoria folosită este O(N2), deoarece folositm o matrice pătratică de dimensiune N.

#include <fstream>

using namespace std;

const int maxn = 101;
const int inf = 1 << 30;

void citire(int D[], int &N)
{
       ifstream in("inmopt.in");

       in >> N;
       for (int i = 0; i <= N; ++i)
       {
              in >> D[i];
       }

       in.close();
}

int rezolvare(int D[], int N)
{
       int M[maxn][maxn];

       for (int i = 1; i <= N; ++i)
       {
              M[i][i] = 0;
       }

       for (int i = N - 1; i; --i)
       {
              for (int j = i + 1; j <= N; ++j)
              {
                     M[i][j] = inf;

                     for (int k = i; k < j; ++k)
                     {
                           int t = M[i][k] + M[k + 1][j] +
                                  D[i - 1] * D[k] * D[j];
                           M[i][j] = min(M[i][j], t);
                     }
              }
       }

       return M[1][N];
}

int main()
{
       int N, D[maxn];

       citire(D, N);

       ofstream out("inmopt.out");
       out << rezolvare(D, N);
       out.close();

       return 0;
}

Exerciții:

a) De ce i trebuie să pornească de la N – 1 și nu de la 1? Ce se întâmplă dacă i merge de la 1 la N?

b) Concepeți o modalitate de a reconstitui soluția. Pentru exemplul dat, o reconstituire a soluției ar putea fi (A1*A2)*A3.

[C++, programare dinamică] Problema submatricei de sumă maximă pe R

Problema este de la finalul acestei pagini (fragment din carte).

c) Se dă o matrice și se cere determinarea unui dreptunghi de sumă maximă. Ultimul algoritm prezentat poate fi extins pentru rezolvarea problemei în O(N3). Cum?


Ultimul algoritmul prezentat în pagina de la linkul de mai sus este:

  • maximul global este inițial primul număr.
  • suma maximă ce se poate obține dintr-o subsecvență care se termină pe poziția primului element este primul element
  • pentru fiecare element de la al doilea până la sfârșit
    • suma maximă a unei subsecvențe ce se termină pe poziția curentă este fie valoarea elementului curent, fie suma obținută dintr-o subsecv. ce se termină pe poziția anterioară + valoarea elementului curent
    • dacă suma maximă obținută pe poziția curentă este > decât maximul global, maximul global devine suma curentă

Problemă similară la sfârșitul capitolului:

  1. Scrieți un program care răspunde eficient la mai multe interogări privind suma unor dreptunghiuri ale unei matrice.

rezolvată ineficient aici. Deosebirea de această problemă pe care am rezolvat-o deja este că nu se cer sume de dreptunghiuri ci un dreptunghi de sumă maximă.

  • nu trebuie să calculez toate sumele ci să calculez inteligent doar sumele necesare dreptunghiului de sumă maximă, dacă e posibil.

Articolul prezent este inspirat din acest articol.

Dată fiind o matrice, găsiți submatricea de sumă maximă din ea. De exemplu, în următoarea matrice, submatricea de sumă maximă este evidențiată cu dreptunghi albastru și suma acestei submatrice este 29.

Problema este mai ales o extensie a problemei subsecvenței de sumă maximă a unui vector.

Soluția naivă pentru această problemă este să se verifice fiecare dreptunghi posibil în matricea dată. Această soluție cere 4 cicluri îmbricate și complexitatea timp a acestei soluții ar fi O(N4). [ n.e. Aici am rezolvat naiv problema. ]

Algoritmul lui Kadane pentru un vector poate fi folosit pentru a reduce complexitatea timp la O(N3). Ideea este să se fixeze coloanele din stânga și din dreapta una câte una și să se găsească rândurile consecutive de sumă maximă pentru fiecare pereche de coloane, una din stânga și una din dreapta. Practic se găsesc numerele de rând de sus și de jos (care au suma maximă) pentru fiecare pereche fixată de coloane din stânga și dreapta. Pentru a găsi numerele de rânduri de sus și de jos, se calculează suma elementelor în fiecare rând de la stânga la dreapta și se stochează aceste sume într-un vector, de exemplu temp[]. Deci temp[i] indică suma elementelor de la stânga la dreapta în rândul i. Dacă se aplică algoritmul lui Kadane pe temp[], și găsim subvectorul de sumă maximă a lui temp, această suma maximă ar fi suma maximă posibilă cu stânga și dreapta ca fiind coloanele mărginitoare. Pentru a găsi suma maximă finală, comparăm această sumă cu suma maximă de până acum.

Metoda descrisă în articol funcționează pentru oricare numere reale.

Cod sursă

#include <fstream>
#include <vector>
using namespace std;

double subsecv_de_suma_maxima(vector<double> &A,
       int &inceput, int &sfarsit)
{
       int N = A.size() - 1;
       double max = A[1];
       int inceput_temp = 1;
       vector<double> S(N + 1);
       S[1] = A[1];
       inceput = sfarsit = 1;

       for (int i = 2; i <= N; ++i)
       {
              if (S[i - 1] + A[i] > A[i])
              {
                     S[i] = S[i - 1] + A[i];
              }
              else
              {
                     inceput_temp = i;
                     S[i] = A[i];
              }

              if (S[i] > max)
              {
                     inceput = inceput_temp;
                     sfarsit = i;
                     max = S[i];
              }
       }

       return max;
}

double suma_max_in_dreptunghi(vector<vector<double>> &D, int r, int c,
       int &stanga, int &dreapta, int &sus, int &jos)
{
       double suma_max = D[1][1];
       for (int st = 1; st <= c; ++st)
       {
              vector<double> temp(r + 1, 0);

              // cand dr == st, e o submatrice-coloana
              for (int dr = st; dr <= c; ++dr)
              {
                     // pt. fiecare rand se adauga elementul curent
                     // din el la elementul corespunzator din temp
                     for (int i = 1; i <= r; ++i)
                     {
                           temp[i] += D[i][dr];
                     }

                     int inceput, sfarsit;

                     double suma = subsecv_de_suma_maxima(temp, inceput, sfarsit);

                     if (suma > suma_max)
                     {
                           suma_max = suma;
                           stanga = st;
                           dreapta = dr;
                           sus = inceput;
                           jos = sfarsit;
                     }
              }
       }
       return suma_max;
}

int main()
{
       int r, c;

       ifstream in("suma.in");
       in >> r >> c;
       vector<vector<double>> D(r + 1, vector<double>(c + 1));
       for (int i = 1; i <= r; ++i)
       {
              for (int j = 1; j <= c; ++j)
              {
                     in >> D[i][j];
              }
       }
       in.close();

       int stanga, dreapta, sus, jos;
       double suma_maxima = suma_max_in_dreptunghi(
              D, r, c, stanga, dreapta, sus, jos);

       ofstream out("suma.out");
       out << suma_maxima << endl;
       out << "(" << sus << ", " << stanga << ")" << endl;
       out << "(" << jos << ", " << dreapta << ")" << endl;
       out.close();

       return 0;
}

Intrare

3 4
0.5 0.1 0.8 -0.9
0.4 0.2  6   0.3
4   0.8  0.9 1

Ieșire

14.1
(1, 1)
(3, 4)

Prezentare

Schemă

[C++, programare dinamică] Problema subsecvenței de produs maxim pe R

Problema este de la finalul acestui fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Enunțul problemei

b) Se cere o subsecvență de produs maxim, iar numerele sunt reale. Rezolvați problema atât pentru numere strict pozitive cât și pentru numere nenule (dar care pot fi negative).
Pentru două rezolvări care se aplică doar asupra numerelor pozitive, sau respectiv doar asupra numerelor întregi, vedeți aici. Tot acolo găsiți intrări de test.
Cod sursă
Soluție inspirată de aici care funcționează în toate cazurile:
  • Nr. întregi: pozitive și negative.
  • Nr. cu virgulă: pozitive și negative.
  • Zero.
Și află și pozițiile de început și de sfârșit ale subsecvenței găsite.

float subsecv(float A[], int N,
       int &inceput, int &sfarsit)
{
       inceput = sfarsit = 1;
       int inceput_pozitiv_temp = 1,
              inceput_negativ_temp = 1;
       vector<float> p(N + 1, 0),
              n(N + 1, 0);
       int zero_index = 0;
       if (A[1] == 0)
       {
              p[1] = n[1] = 0;
              zero_index = 1;
       }
       else if (A[1] > 0)
       {
              p[1] = A[1];
              n[1] = 0;
       }
       else // A[1] < 0
       {
              p[1] = 0;
              n[1] = A[1];
       }
       float maximul = A[1];
       for (int i = 2; i <= N; ++i)
       {
              if (A[i] == 0)
              {
                     p[i] = n[i] = 0;
                     if (zero_index == 0)
                     {
                           zero_index = i;
                     }
              }
              else if (A[i] > 0)
              {
                     if (A[i] > A[i] * p[i – 1])
                     {
                           p[i] = A[i];
                           inceput_pozitiv_temp = i;
                     }
                     else
                     {
                           p[i] = A[i] * p[i – 1];
                     }
                     n[i] = A[i] * n[i – 1];
              }
              else // A[i] < 0
              {
                     p[i] = A[i] * n[i – 1];
                     inceput_pozitiv_temp = inceput_negativ_temp;
                     if (A[i] < A[i] * p[i – 1])
                     {
                           n[i] = A[i];
                           inceput_negativ_temp = i;
                     }
                     else
                     {
                           n[i] = A[i] * p[i – 1];
                           inceput_negativ_temp = inceput_pozitiv_temp;
                     }
              }
              if (p[i] > maximul)
              {
                     maximul = p[i];
                     inceput = inceput_pozitiv_temp;
                     sfarsit = i;
              }
       }
       if (maximul > 0)
       {
              return maximul;
       }
       if (zero_index != 0)
       {
              inceput = sfarsit = zero_index;
              return 0;
       }
       inceput = sfarsit = 1;
       return A[1];
}


Explicații
Dată fiind prima soluție de aici (titlul „Cod sursă”) se încearcă adaptarea ei pentru a funcționa și pentru numere negative și zero.
Dat fiind vectorul A cu indici de la 1 la N, lăsăm p[i] să fie produsul maxim pozitiv al unei subsecvențe din A[1, i] conținând A[i], și lăsăm pe n[i] să fie produsul minim negativ al unei asemenea subsecvențe. Dacă nici o asemenea subsecvență nu există, lăsăm p[i] = 0 sau n[i] = 0.
Inițializare:
  • dacă A[1] = 0, atunci p[1] = n[1] = 0
  • dacă A[1] > 0, atunci p[1] = A[1] și n[1] = 0
  • dacă A[1] < 0, atunci p[1] = 0 și n[1] = A[1]
Iterare:
  • dacă A[i] = 0, atunci p[i] = n[i] = 0
  • dacă A[i] > 0, atunci p[i] = max(A[i], A[i] * p[i – 1]) și n[i] = A[i] * n[i – 1]
  • dacă A[i] < 0, atunci p[i] = A[i] * n[i – 1] și n[i] = min(A[i], A[i] * P[i – 1])
Dacă max(p[1], …, p[N]) > 0, atunci acesta este răspunsul. Unicul mod în care aceasta nu are loc este dacă nu există o subsecvență al cărei produs să fie pozitiv. Aceasta poate avea loc doar dacă vectorul conține doar numere negative și zerouri, și fiecare două numere negative sunt separate prin cel puțin un zero. Dacă există cel puțin un zero, atunci răspunsul este zero. Dacă nu există zerouri, atunci N = 1 și răspunsul este A[1].

[C++, programare dinamică] Problema celui mai lung subșir comun

Se dau două șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Se cere găsirea unui șir de caractere C de lungime maximă care este subșir atât a lui A cât și a lui B.
Șirurile A și B se citesc din fișierul sircom.in, fiecare pe câte o linie. In fișierul sircom.out se va afișa pe prima linie lungimea celui mai lung subșir comun, iar pe a doua linie șirul găsit.

Rezolvare

Pentru a rezolva problema vom încerca să găsim o formulă de recurență pentru calculul lungimii celui mai lung subșir comun. Fie L[i][j] = lungimea celui mai lung subșir comun al subsecvențelor A[1, i] și B[1, j], pentru 1 ≤ i ≤ lungime(A) și 1 ≤ j ≤ lungime(B). Să presupunem că avem calculate toate valorile matricii L care preced elementul (p + 1, q + 1) (sunt fie pe aceeași linie și pe o coloană precedentă, fie pe o linie precedentă). Se disting două cazuri:
  1. Dacă A[p + 1] == B[q + 1], atunci putem adăuga caracterul A[p + 1] celui mai lung subșir comun al secvențelor A[1, p] și B[1, q], obținând, pentru secvențele A[1, p + 1] și B[1, q + 1] un subșir comun de lungime maximă care este mai lung cu un caracter. Așadar, L[p + 1][q + 1] = L[p][q] + 1.
  2. Dacă A[p + 1] != B[q + 1], atunci nu putem extinde niciun subșir de lungime maximă calculat anterior și va trebui să salvăm în L[p + 1][q + 1] lungimea celui mai lung subșir de lungime maximă calculat până acuma. Această valoare este dată de maximul dintre L[p][q + 1] și L[p + 1][q].
Timpul de execuție al acestei metode este O(N·M), unde N este lungimea primului șir, iar M este lungimea celui de-al doilea șir. Memoria folosită de algoritm este tot O(N·M), deoarece matricea L are N linii și M coloane. Putem reduce memoria folosită la O(N + M), dar sacrificăm astfel posibilitatea reconstituirii soluției. Vom descrie însă și această metodă.

Pentru a reconstitui soluția vom proceda similar cu metoda de reconstituire a unui drum a cărui lungime minimă a fost calculată cu algoritmul lui Lee. Vom folosi o functie recursivă reconst(x, y) care va afișa un subșir comun de lungime maximă. In primul rând, condiția de ieșire din recursivitate va fi dacă x < 1 sau y < 1. Dacă nu, verificăm dacă A[x] == B[y], iar dacă da, apelăm recursiv reconst(x – 1, y – 1) și afișăm A[x]. Dacă A[x] != B[y] atunci apelăm recursiv fie reconst(x – 1, y), în cazul în care L[x – 1][y] > L[x][y – 1], fie reconst(x, y – 1) altfel.

Pentru a simplifica implementarea am folosit tipul de date string pentru reținerea șirurilor de caractere. Indicii șirurilor de caractere încep de la 0, așa că trebuie să fim atenți la cum comparăm caracterele individuale, deoarece indicii matricei L încep de la 1. Singura inițializare care trebuie făcută este completarea liniei și coloanei 0 a matricei L cu valoarea 0, pentru a evita cazurile particulare ale recurenței descrise.

Prezentăm în continuare implementarea algoritmului de rezolvare.


Pentru a reduce memoria folosită la O(N + M) trebuie observat că pentru calculul unei valori L[i][j] nu avem nevoie decât de valori de pe linia curentă (L[i][j – 1]) și de pe linia precedentă (L[i – 1][j] și L[i – 1][j – 1]). Așadar, este de ajuns să folosim doar doi vectori de lungime egală cu lungimea șirului B. Unul dintre vectori, L1 va reprezenta linia precedentă liniei curente, iar celălalt vector, L2, va reprezenta chiar linia curentă. Noua formă a formulei de recurență este:

După fiecare calculare completă a lui L2, înainte de începerea unei noi iterații vectorul L2 va trebui copiat în L1, pentru ca valorile calculate la pasul curent să poată fi folosite la pasul următor. La sfârșitul algoritmului, cei doi vectori vor avea același conținut, deci răspunsul problemei va fi dat fie de L1[lungime(B)] fie de L2[lungime(B)].

Prezentăm doar modificările relevante:

Această implementare este preferabilă dacă memoria disponibilă este limitată și dacă nu se cere reconstituirea unei soluții, acest lucru fiind imposibil deoarece algoritmul păstrează doar valorile finale ale recurenței, nu și pe cele inițiale.

Exerciții:

a) Afișați întreaga matrice L pentru a înțelege mai bine formula de recurență.

b) Afișați toate subșirurile comune de lungime maximă.

c) In implementarea de mai sus am transmis parametrii A și B prin referință. Unde era indicat să se folosească transmitere prin referință constantă?

d) Scrieți o implementare care folosește vectori clasici de caractere în loc de tipul string.

e) Scrieți un program care afișează acel subșir comun de lungime maximă care este primul din punct de vedere alfabetic.

f) Se poate evita copierea vectorului L2? Dacă da, cum?