Articolele lui Candale Silviu (silviu)

Introducere

Există numeroase probleme cu cifrele unui număr și multe dintre ele se pot rezolva cu ajutorul unei funcții – chiar recursive:

• suma cifrelor unui număr; suma cifrelor de unu numit tip (pare/impare, etc.);
• numărul de cifre; numărul de cifre de un anumit tip (pare/impare, etc.);
• construirea unui număr folosind anumite cifre din numărul dat;
• etc.

Pentru realizarea unei funcții recursive, care determină rezultatul cerut, folosim un algoritm de forma următoare:

• identificăm cazul particular;
• dacă suntem în cazul particular, obținem rezultatul în mod direct;
• dacă nu suntem în cazul particular:
  • rezolvăm, prin autoapel, problema pentru numărul fără ultima cifră;
  • cu rezultatul obținut și ultima cifră obținem rezultatul final, pentru numărul dat.

Desigur, algoritmul de mai sus trebuie adaptat la specificul problemei, dar în majoritatea situațiilor el este de acest tip!

Exemplu

Pentru a determina suma cifrelor unui număr procedăm astfel:

• antetul funcției va fi: int sumcif(int n)
• cazul particular poate fi când numărul este 0 (n==0). În acest caz rezultatul este 0;
• dacă n>0, determinăm rezultatul pentru numărul fără ultima cifră: S = sumcif(n/10);
• rezultatul final va fi S + n % 10 – suma cifrelor numărului fără ultima cifră, adunată cu ultima cifră a lui n.

Puse împreună, obținem:

int sumcif(int n)
{
	if(n == 0)
    	return 0;
    else
   	{
    	int S = sumcif(n/10);
        return S + n%10;
    }
}

Un alt exemplu, parțial corect

Funcția de mai sus este corectă, dând rezultatul valid pentru orice valoarea număr natural a paramatrului (valoare care se încadrează in tipul int, bineînțeles). Pe de altă parte, dacă vom scrie o funție pe același model pentru numărul de cifre, am obține:

int nrcif(int n)
{
	if(n == 0)
    	return 0;
    else
   	{
    	int S = nrcif(n/10);
        return S + 1;
    }
}

Dar funcția de mai sus este corectă numai pentru n>0. Apelul nrcif(0) dă rezultatul 0 – greșit, deoarece numărul zero conține 1 cifră.

De ce nu este corect?!

Condiția n == 0 poate fi adevărată în două situații, pentru care funcția trebuie să returneze valori diferite:

• dacă n devine 0 în urma autoapelurilor, funcția trebuie să returneze 0 – suntem în situația în care avem un număr “fără cifre”!
• dacă n este zero în apelul principal, funcția trebuie să returneze 1 – ne interesează efectiv câte cifre are 0 – are o cifră.

La apelul funcției nu putem știi în ce situație ne aflăm, așa că nu putem stabili valoarea care trebuie returnată!

Cum corectăm?!

Soluția este simplă: considerăm cazul particular când numărul are o cifră (n<0), nu când este egal cu 0. Funcția pentru numărul de cifre devine:

int nrcif(int n)
{
	if(n < 10)
    	return 1;
    else
   	{
    	int S = nrcif(n/10);
        return S + 1;
    }
}

Important

Pentru funcțiile recursive care prelucrează cifrele unui număr (n) considerăm cazul particular când numărul are o singură cifră (n<10), nu când numărul este zero (n==0)!

Last updated: September 06, 2023

This Privacy Policy describes Our policies and procedures on the collection, use and disclosure of Your information when You use the Service and tells You about Your privacy rights and how the law protects You.

We use Your Personal data to provide and improve the Service. By using the Service, You agree to the collection and use of information in accordance with this Privacy Policy. This Privacy Policy has been created with the help of the Free Privacy Policy Generator.

Interpretation and Definitions

Interpretation

The words of which the initial letter is capitalized have meanings defined under the following conditions. The following definitions shall have the same meaning regardless of whether they appear in singular or in plural.

Definitions

For the purposes of this Privacy Policy:

• Account means a unique account created for You to access our Service or parts of our Service.
• Affiliate means an entity that controls, is controlled by or is under common control with a party, where "control" means ownership of 50% or more of the shares, equity interest or other securities entitled to vote for election of directors or other managing authority.
• Company (referred to as either "the Company", "We", "Us" or "Our" in this Agreement) refers to PbInfo.
• Cookies are small files that are placed on Your computer, mobile device or any other device by a website, containing the details of Your browsing history on that website among its many uses.
• Country refers to: Romania
• Device means any device that can access the Service such as a computer, a cellphone or a digital tablet.
• Personal Data is any information that relates to an identified or identifiable individual.
• Service refers to the Website.
• Service Provider means any natural or legal person who processes the data on behalf of the Company. It refers to third-party companies or individuals employed by the Company to facilitate the Service, to provide the Service on behalf of the Company, to perform services related to the Service or to assist the Company in analyzing how the Service is used.
• Usage Data refers to data collected automatically, either generated by the use of the Service or from the Service infrastructure itself (for example, the duration of a page visit).
• Website refers to PbInfo, accessible from https://www.pbinfo.ro
• You means the individual accessing or using the Service, or the company, or other legal entity on behalf of which such individual is accessing or using the Service, as applicable.

Collecting and Using Your Personal Data

Types of Data Collected

Personal Data

While using Our Service, We may ask You to provide Us with certain personally identifiable information that can be used to contact or identify You. Personally identifiable information may include, but is not limited to:

• Email address
• First name and last name
• School, City, Province
• Usage Data

Usage Data

Usage Data is collected automatically when using the Service.

Usage Data may include information such as Your Device’s Internet Protocol address (e.g. IP address), browser type, browser version, the pages of our Service that You visit, the time and date of Your visit, the time spent on those pages, unique device identifiers and other diagnostic data.

When You access the Service by or through a mobile device, We may collect certain information automatically, including, but not limited to, the type of mobile device You use, Your mobile device unique ID, the IP address of Your mobile device, Your mobile operating system, the type of mobile Internet browser You use, unique device identifiers and other diagnostic data.

We may also collect information that Your browser sends whenever You visit our Service or when You access the Service by or through a mobile device.

Tracking Technologies and Cookies

We use Cookies and similar tracking technologies to track the activity on Our Service and store certain information. Tracking technologies used are beacons, tags, and scripts to collect and track information and to improve and analyze Our Service. The technologies We use may include:

• Cookies or Browser Cookies. A cookie is a small file placed on Your Device. You can instruct Your browser to refuse all Cookies or to indicate when a Cookie is being sent. However, if You do not accept Cookies, You may not be able to use some parts of our Service. Unless you have adjusted Your browser setting so that it will refuse Cookies, our Service may use Cookies.
• Web Beacons. Certain sections of our Service and our emails may contain small electronic files known as web beacons (also referred to as clear gifs, pixel tags, and single-pixel gifs) that permit the Company, for example, to count users who have visited those pages or opened an email and for other related website statistics (for example, recording the popularity of a certain section and verifying system and server integrity).

Cookies can be "Persistent" or "Session" Cookies. Persistent Cookies remain on Your personal computer or mobile device when You go offline, while Session Cookies are deleted as soon as You close Your web browser. Learn more about cookies on the Free Privacy Policy website article.

We use both Session and Persistent Cookies for the purposes set out below:

Necessary / Essential Cookies

• Type: Session Cookies
• Administered by: Us
• Purpose: These Cookies are essential to provide You with services available through the Website and to enable You to use some of its features. They help to authenticate users and prevent fraudulent use of user accounts. Without these Cookies, the services that You have asked for cannot be provided, and We only use these Cookies to provide You with those services.

Cookies Policy / Notice Acceptance Cookies

• Type: Persistent Cookies
• Administered by: Us
• Purpose: These Cookies identify if users have accepted the use of cookies on the Website.

Functionality Cookies

• Type: Persistent Cookies
• Administered by: Us
• Purpose: These Cookies allow us to remember choices You make when You use the Website, such as remembering your login details or language preference. The purpose of these Cookies is to provide You with a more personal experience and to avoid You having to re-enter your preferences every time You use the Website.

For more information about the cookies we use and your choices regarding cookies, please visit our Cookies Policy or the Cookies section of our Privacy Policy.

Use of Your Personal Data

The Company may use Personal Data for the following purposes:

• To provide and maintain our Service, including to monitor the usage of our Service.
• To manage Your Account: to manage Your registration as a user of the Service. The Personal Data You provide can give You access to different functionalities of the Service that are available to You as a registered user.
• For the performance of a contract: the development, compliance and undertaking of the purchase contract for the products, items or services You have purchased or of any other contract with Us through the Service.
• To contact You: To contact You by email, telephone calls, SMS, or other equivalent forms of electronic communication, such as a mobile application’s push notifications regarding updates or informative communications related to the functionalities, products or contracted services, including the security updates, when necessary or reasonable for their implementation.
• To provide You with news, special offers and general information about other goods, services and events which we offer that are similar to those that you have already purchased or enquired about unless You have opted not to receive such information.
• To manage Your requests: To attend and manage Your requests to Us.
• For business transfers: We may use Your information to evaluate or conduct a merger, divestiture, restructuring, reorganization, dissolution, or other sale or transfer of some or all of Our assets, whether as a going concern or as part of bankruptcy, liquidation, or similar proceeding, in which Personal Data held by Us about our Service users is among the assets transferred.
• For other purposes: We may use Your information for other purposes, such as data analysis, identifying usage trends, determining the effectiveness of our promotional campaigns and to evaluate and improve our Service, products, services, marketing and your experience.
• We may share Your personal information in the following situations:
  • With Service Providers: We may share Your personal information with Service Providers to monitor and analyze the use of our Service, to contact You.
  • For business transfers: We may share or transfer Your personal information in connection with, or during negotiations of, any merger, sale of Company assets, financing, or acquisition of all or a portion of Our business to another company.
  • With Affiliates: We may share Your information with Our affiliates, in which case we will require those affiliates to honor this Privacy Policy. Affiliates include Our parent company and any other subsidiaries, joint venture partners or other companies that We control or that are under common control with Us.
  • With business partners: We may share Your information with Our business partners to offer You certain products, services or promotions.
  • With other users: when You share personal information or otherwise interact in the public areas with other users, such information may be viewed by all users and may be publicly distributed outside.
  • With Your consent: We may disclose Your personal information for any other purpose with Your consent.

Retention of Your Personal Data

The Company will retain Your Personal Data only for as long as is necessary for the purposes set out in this Privacy Policy. We will retain and use Your Personal Data to the extent necessary to comply with our legal obligations (for example, if we are required to retain your data to comply with applicable laws), resolve disputes, and enforce our legal agreements and policies.

The Company will also retain Usage Data for internal analysis purposes. Usage Data is generally retained for a shorter period of time, except when this data is used to strengthen the security or to improve the functionality of Our Service, or We are legally obligated to retain this data for longer time periods.

Transfer of Your Personal Data

Your information, including Personal Data, is processed at the Company’s operating offices and in any other places where the parties involved in the processing are located. It means that this information may be transferred to — and maintained on — computers located outside of Your state, province, country or other governmental jurisdiction where the data protection laws may differ than those from Your jurisdiction.

Your consent to this Privacy Policy followed by Your submission of such information represents Your agreement to that transfer.

The Company will take all steps reasonably necessary to ensure that Your data is treated securely and in accordance with this Privacy Policy and no transfer of Your Personal Data will take place to an organization or a country unless there are adequate controls in place including the security of Your data and other personal information.

Delete Your Personal Data

You have the right to delete or request that We assist in deleting the Personal Data that We have collected about You.

Our Service may give You the ability to delete certain information about You from within the Service.

You may update, amend, or delete Your information at any time by signing in to Your Account, if you have one, and visiting the account settings section that allows you to manage Your personal information. You may also contact Us to request access to, correct, or delete any personal information that You have provided to Us.

Please note, however, that We may need to retain certain information when we have a legal obligation or lawful basis to do so.

Disclosure of Your Personal Data

Business Transactions

If the Company is involved in a merger, acquisition or asset sale, Your Personal Data may be transferred. We will provide notice before Your Personal Data is transferred and becomes subject to a different Privacy Policy.

Law enforcement

Under certain circumstances, the Company may be required to disclose Your Personal Data if required to do so by law or in response to valid requests by public authorities (e.g. a court or a government agency).

Other legal requirements

The Company may disclose Your Personal Data in the good faith belief that such action is necessary to:

• Comply with a legal obligation
• Protect and defend the rights or property of the Company
• Prevent or investigate possible wrongdoing in connection with the Service
• Protect the personal safety of Users of the Service or the public
• Protect against legal liability

Security of Your Personal Data

The security of Your Personal Data is important to Us, but remember that no method of transmission over the Internet, or method of electronic storage is 100% secure. While We strive to use commercially acceptable means to protect Your Personal Data, We cannot guarantee its absolute security.

Children’s Privacy

Our Service does not address anyone under the age of 13. We do not knowingly collect personally identifiable information from anyone under the age of 13. If You are a parent or guardian and You are aware that Your child has provided Us with Personal Data, please contact Us. If We become aware that We have collected Personal Data from anyone under the age of 13 without verification of parental consent, We take steps to remove that information from Our servers.

If We need to rely on consent as a legal basis for processing Your information and Your country requires consent from a parent, We may require Your parent’s consent before We collect and use that information.

Links to Other Websites

Our Service may contain links to other websites that are not operated by Us. If You click on a third party link, You will be directed to that third party’s site. We strongly advise You to review the Privacy Policy of every site You visit.

We have no control over and assume no responsibility for the content, privacy policies or practices of any third party sites or services.

Changes to this Privacy Policy

We may update Our Privacy Policy from time to time. We will notify You of any changes by posting the new Privacy Policy on this page.

We will let You know via email and/or a prominent notice on Our Service, prior to the change becoming effective and update the "Last updated" date at the top of this Privacy Policy.

You are advised to review this Privacy Policy periodically for any changes. Changes to this Privacy Policy are effective when they are posted on this page.

Contact Us

If you have any questions about this Privacy Policy, You can contact us:

• By visiting this page on our website: https://www.pbinfo.ro/?pagina=contact-form

La concursul Mate Info UBB, ediția 2021 a fost dat următorul exercițiu:

Răspunsul corect este: A, B, D.

Varianta C. se elimină imediat, deoarece reprezentarea binară a lui 3 este 11, iar suma cifrelor binare este 2, nedivizibil cu 3.

Pentru a demonstra că afirmațiile A., B. și D. sunt adevărate vom demonstra următoarea afirmație, mai generală.

Teoremă: Fie \(N\) un număr natural a cărui reprezentare în baza \(B\) este \(b_nb_{n-1}…b_0\). Numărul \(N\) este divizibil cu \(B+1\) dacă și numai dacă expresia \(E = b_0-b_1+b_2-b_3+…..+(-1)^n *b_n\) este divizibilă \(B+1\).

Pentru a demonstra teorema de mai sus, vom demonstra mai întâi următoarea lemă:

Lemă: Fie \(P\) un număr natural. Atunci \(P^{2k}\) este de forma \(X \cdot (P+1)+1\), iar \(P^{2k+1}\) este de forma \(Y \cdot (P+1)-1\)

Demonstrația lemei se face prin inducție. Mai întâi să observăm că \(P^{0} = 1 = 0 \cdot (P+1) + 1\), iar \(P^{1} = P = 1 \cdot (P+1) – 1\).

Dacă \(P^{2k} = X \cdot (P+1)+1\), atunci \(P^{2k+1} = P \cdot P^{2p} \\= P \cdot (X \cdot (P+1)+1) \\= P \cdot X \cdot (P+1)+P \\= P \cdot X \cdot (P+1)+P + 1 – 1 \\= (P \cdot X+1)\cdot(P+1)-1 \\= Y \cdot (P+1) -1\)

Similar, dacă \(P^{2k+1} = Y \cdot (P+1)-1\), atunci \(P^{2k+2} = P \cdot P^{2k+1} \\= P \cdot (Y \cdot (P+1) -1) \\= P \cdot Y \cdot (P + 1) – P \\= P \cdot Y \cdot (P + 1) – P – 1 + 1 \\= P \cdot Y \cdot (P + 1) – (P + 1) + 1 \\= (P \cdot Y -1) \cdot (P + 1) + 1 \\= X \cdot (P+1) + 1\)

Demonstrația teoremei Dacă \(b_nb_{n-1}…b_0\) este reprezentarea în baza \(B\) a lui \(N\), atunci

$$N=b_0 \cdot B^0 + b_1 \cdot B^1 + b_2 \cdot B^2 + b_3 \cdot B^3 + … + b_n \cdot B^n$$

Deoarece puterile lui \(B\) sunt de forma precizată în lemă, obținem:

$$\begin{aligned} N &= b_0 \cdot ((B+1) \cdot f_0 + 1) + b_1 \cdot ((B+1) \cdot f_1 – 1) + b_2 \cdot ((B+1) \cdot f_2 + 1) + b_3 \cdot ((B+1) \cdot f_3 – 1) + \cdots + b_n \cdot ((B+1) \cdot f_n + (-1)^n) \\
& = ((B+1) \cdot b_0 \cdot f_0 + b_0) + ((B+1) \cdot b_1 \cdot f_1 – b_1) + ((B+1) \cdot b_2 \cdot f_2 + b_2) + ((B+1) \cdot b_3 \cdot f_3 – b_3) + \cdots + ((B+1) \cdot b_n \cdot f_n + (-1)^n \cdot b_n)\\
& = (B+1) \cdot b_0 \cdot f_0 + (B+1) \cdot b_1 \cdot f_1 + (B+1) \cdot b_2 \cdot f_2 + (B+1) \cdot b_3 \cdot f_3 + \cdots + (B+1) \cdot b_n \cdot f_n + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot ( b_0 \cdot f_0 + \cdot f_1 + b_2 \cdot f_2 + \cdot b_3 \cdot f_3 + \cdots + \cdot b_n \cdot f_n) + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
& = (B+1) \cdot M + b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\\
\end{aligned}$$

Deoarece \((B+1) \cdot M\) este divizibil cu \(B+1\), deducem că \(N\) este divizibil cu \(B+1\) dacă și numai dacă \(b_0 – b_1 + b_2 – b_3 + \cdots + (-1)^n \cdot b_n\) este divizibil cu \(B+1\)!

Observații:

Exercițiul de mai sus este un caz particular al teoremei, în care \(B = 2\).

Expresia \(E\) poate fi scrisă și \(E = (b_0 + b_2 + …) – (b_1 + b_3 + …)\) – diferența dintre suma cifrelor de rang par și suma cifrelor de rang impar. Dacă \(B=10\), proprietatea de mai sus este “Criteriul de divizibilitate cu 11”.

Acest articol conține o listă cu subiecte date la examenul de bacalaureat, clasificate în funcție de problema ce presupune analiza algoritmilor pseudocod. Lista poate fi filtrată după an, categoria problemei și tipul structurii repetitive utilizate.

Citiți mai întâi Generarea aranjamentelor!

Introducere

Consideram o mulțime cu A cu n elemente. Prin combinări de k elemente din A înțelegem submulțimile cu k elemente ale multimii A. Numărul acestor combinări este \(C_n^k = \frac{A_n^k}{P_k}\). Mai multe formule pentru calculul numărului de combinări pot fi găsite în acest articol.

Acest articol prezintă un algoritm backtracking pentru determinarea în ordine lexicografică a combinărilor de k elemente ale mulțimii A={1 , 2 , ... , n}, elemente dintr-o combinare fiind generate în ordine crescătoare. El poate fi adaptat pentru determinarea combinărilor de k elemente ale unei mulțimi oarecare de n elemente.

Deoarece în algoritmul recursiv general apare funcția Back() cu parametrul k, pentru a păstra notațiile din algoritm vom considera în continuare combinările de k elemente luate câte p.

Soluția 1

Condiții

Ca orice rezolvare cu algoritmul backtracking, începem prin a preciza semnificația vectorului soluție. Astfel, x[] reprezintă o combinare. În consecință, el va respecta următoarele condiții:

• elemenele vectorului sunt valori între 1 și n;
• elementele nu se repetă;
• elementele sunt ordonate crescător
• vectorul se completează element cu element. Când va avea p elemente, reprezintă o combinare completă, care urmează a fi afișată.

Formal, exprimăm proprietățile de mai sus astfel:

• condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
• condiții interne:
  • \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
  • \(x[k] > x[k-1]\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
• condiții de existență a soluției: \(k = p\)

Observăm (din nou) că în verificarea condițiilor interne intervine doar elementul x[k] (cel care este verificat) și elementele deja generate (x[1], x[2], … , x[k-1]).

Observăm că aceste condiții sunt cele de la generarea aranjamentelor, la care se adaugă condiția internă legată de ordinea elementelor din vector. În consecință, programul va fi cel de la aranjamente, cu completarea funcției OK().

Sursa C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    if(k > 1)
		if(x[k] <= x[k-1])
			return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    back(1);
    return 0;
}

Soluția 2

Rafinarea condițiilor

Condițiile de mai sus pot fi îmbunătățite, făcând următoarele observații:

1. cele două condiții interne pot fi reduse la una singură. Dacă pentru fiecare \( k \) are loc relația \(x[k] > x[k-1]\) atunci are loc și condiția \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\);
   Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
   • condiții interne: \(x[k] > x[k-1]\), pentru \( k > 1 \)
   • condiții de existență a soluției: \(k = p\)
2. condiția internă poate fi transformată în condiție externă. Dacă \(x[k] > x[k-1]\) atunci valorile pe care le poate lua \(x[k]\) (condiții externe) sunt \( \left\{ x[k-1] + 1, \ldots, n \right\} \). Condițiile devin:
   • condiții externe: \( x[k] \in \left\{ x[k-1] +1 , x[k-1] +2, \ldots, n \right\} \);
   • condiții interne: nu există
   • condiții de existență a soluției: \(k = p\)

Cazul \(k = 1\) este unul special. Valorile pe care le poate lua sunt \(\left\{ 1 , 2 , 3 , \ldots \right\} \). Pentru a fi condițiile externe de mai sus corecte în în acest caz, este necesară inițializarea x[ 0 ] = 0, înaintea începerii generării.

Sursă C++

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

void back(int k){
    for(int i = x[k-1] + 1 ; i <= n ; ++ i)
    {
        x[k] = i;
		if(k == p)
			Afis(k);
		else
			back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    x[0] = 0;
    back(1);
    return 0;
}

Probleme

combinari combinari2 siruri SubmDiv cifre_c subimp2

Citește și

• Prezentare generală
• Generarea permutărilor
• Generarea aranjamentelor

• Generarea submulțimilor

Citiți mai întâi Generarea permutărilor!

Introducere

Considerăm o mulțime cu n elemente. Prin aranjamente de k elemente din acea mulțime înțelegem șirurile de k elemente din ea. Două șiruri diferă prin valorile elementelor sau prin ordinea acestora.

Numărul acestor șiruri este aranjamente de n luate câte k, adică \(A_n^k = n \cdot (n-1) \cdot \ldots \cdot(n – k +1) \).

Acest articol prezintă algoritmul de generare în ordine lexicografică a aranjamentelor de k elemente ale mulțimii {1, 2, ..., n}. El poate fi ușor modificat pentru a genera aranjamentele unei mulțimi cu elemente oarecare.

Metoda folosită va fi backtracking, varianta recursivă. Deoarece în algoritmul de generare folosit intervine variabila k, ca parametru al funcției Back(), vom considera în continuare aranjamentele de n elemente luate câte p.

Exemplu

Pentru n = 4 și p = 3 vom avea 4 * 3 * 2 = 24 de aranajamente. Lista completă a acestora este:

1 2 3		2 1 3		3 1 2		4 1 2
1 2 4		2 1 4		3 1 4		4 1 3
1 3 2		2 3 1		3 2 1		4 2 1
1 3 4		2 3 4		3 2 4		4 2 3
1 4 2		2 4 1		3 4 1		4 3 1
1 4 3		2 4 3		3 4 2		4 3 2

Condiții

În rezolvarea problemei intervine vectorul soluție, x[]. Acesta reprezintă un aranjament candidat, care va deveni la un moment dat un aranjament de p elemente complet. Proprietățile vectorului soluție sunt cele specifice aranjamentelor:

• elementele sunt din mulțimea dată, adică numere intre 1 și n;
• elementele nu se repetă;
• vectorul se completează element cu element. Când va avea p elemente, reprezintă un aranjament complet, care urmează a fi afișat.

Formal, exprimăm proprietățile de mai sus astfel:

• condiții externe: \( x[k] \in \left\{ 1,2, \ldots, n \right\} \);
• condiții interne: \(x[k] \notin \left\{ x[ 1 ],x[ 2 ], \ldots, x[ k-1 ] \right\}\), pentru \( k \in \left\{2,3, \ldots, n \right \} \)
• condiții de existență a soluției: \(k = p\)

Sursă C++

Următorul program afișează pe ecran aranjamantele de n alemente luate câte p, în ordine lexicografică, folosind un algoritm recursiv:

#include <iostream>
using namespace std;

int x[10] , n , p;

void Afis(int k)
{
    for(int j = 1 ; j <= k ; j ++)
        cout << x[j] << " ";
    cout << endl;
}

bool OK(int k){
    for(int i = 1 ; i < k ; ++ i)
        if(x[k] == x[i])
            return false;
    return true;
}

bool Solutie(int k)
{
    return k == p;
}

void Back(int k){
    for(int i = 1 ; i <= n ; ++ i)
    {
        x[k] = i;
        if(OK(k))
            if(Solutie(k))
                Afis(k);
            else
                Back(k + 1);
    }
}
int main(){
    cin >> n >> p;
    Back(1);
    return 0;
}

Se poate observa că atât condițiile descrise mai sus, cât și algoritmul de generare sunt foarte asemănătoare cu cele de la generarea permutărilor.

Acest lucru se datorează faptului că, la ambele probleme, vectorii soluție identici în ceea ce privește conținutul: șiruri de elemente diferite cuprinse între 1 și n. Diferă numai lungimea lor – momentul când vectorul soluție x[] conține o soluție completă:

• la problema permutărilor un vector soluție final are n elemente (toate elementele mulțimii date, într-o anumită ordine);
• la problema aranjamentelor un vector soluție final are p elemente (p elemente dintre cele n ale mulțimii date, într-o anumită ordine).

La fel ca în cazul generării permutărilor, și pentru această problemă se pot scrie soluții iterative, precum și soluții în care verificarea condițiilor interne să se facă cu un vector caracteristic, evitându-se parcurgerile repetate ale vectorului soluție.

Probleme propuse

196 3159

Citește și

• Prezentare generală
• Generarea permutărilor

• Generarea combinărilor
• Generarea submulțimilor

Tipul char este folosit pentru lucrul cu caractere. O dată de acest tip va reprezenta un singur caracter. Pentru a stoca mai multe caractere vom folosi un tablou cu elemente char sau un string.

Variabile de tip char

O variabilă de tip char se declară astfel:

char C;

Valoarea unei variabile de tip char (sau signed char) este un număr natural cuprins între -128 și 127. Valorile cuprinse între 0 și 127 corespund caracterelor din codul ASCII.

Similar, datele de tip unsigned char au valori între 0 și 255. Observăm că ambele tipuri conțin valorile care corespund caracterelor din codul ASCII.

Literali

Un literal (valoare) de tip char este un caracter din codul ASCII, delimitat de caractere apostrof ‘.

Putem inițializa o variabilă de tip char atribuindu-i un literal de tip char sau o valoare numerică. Dacă valoarea numerică nu aparține intervalului de valori corespunzător, aceasta va fi trunchiată.

char C;
C = 'A';
C = 65;

Atenție! “ – ghilimele delimitează șiruri de caractere. Un șir de caractere format dintr-un singur caracter nu este același lucru cu un caracter.
“A” ≠ ‘A’!

Afișarea și citirea

Deși datele de tip char memorează numere întregi, la citirea și afișarea lor se va lucra cu caractere.

Afișarea

char C = 'A';
cout << C; // A
C = 65;
cout << C; // A

Afișarea unei date de tip char se face astfel:

• dacă valoarea este din codul ASCII, se va afișa caracterul corespunzător. Pentru caracterele neimprimabile efectul depinde de caracter și de mediul în care se lucrează (este posibil să nu se afișeze nimic sau să se afișeze diverse simboluri).
• dacă valoarea este din afara codului ASCII, efectul depinde de mediul în care se lucrează.

Citirea

char C;
cin >> C;
...

În urma citirii de la tastatură unei variabile de tip char, aceasta va reprezenta caracterul introdus. Dacă se introduc mai multe caractere, se va citi doar primul dintre ele.

Exemple

char x;
cin >> x; // introducem A
cout << x; // A

char x;
cin >> x; // introducem 145
cout << x; // 1

char x, y;
cin >> x >> y; // introducem A B
cout << x << endl; // A 
cout << y << endl; // B	

char x, y;
cin >> x >> y; // introducem AB
cout << x << endl; // A 
cout << y << endl; // B

char x, y;
cin >> x >> y; // introducem ABC
cout << x << endl; // A 
cout << y << endl; // B

char x, y;
cin >> x >> y; // introducem 65 66
cout << x << endl; // 6
cout << y << endl; // 5

Operații. Conversii de tip

Valorile de tip char pot fi convertite la alte tipuri.

char x;
x = 65; // conversie implicită de la int la char
cout << x; // A
cout << (int) x; // 65
int n = 65;
cout << (char) n; //A

Cu datele de tip char se pot face toate operațiile uzuale cu numere. Valoarea de tip char va fi convertită implicit la int, apoi se vor face operațiile.

char x = 'A';
cout << x + 1; // 66
cout << (char)(x + 1); // B

char x = 'A';
x ++;
cout << x; // B

Transformarea între litere mari și mici

O problemă frecventă este determinarea, pentru o literă mare, a literei mici corespunzătoare, sau invers. Rezolvarea se bazează pe faptul că, în codul ASCII, literele mari sunt poziționate înaintea celor mici, iar diferența dintre codul ASCII a unei litere mici și codul ASCII a literei mari corespunzătoare este aceeași pentru toate literele (32).

Transformarea se va face scăzând această valoare din litera mică, sau adunând-o la litere mare:

int dif = 'a' - 'A'; // 32
char x = 'k';
x = x - dif;
cout << x; // K

C++ ne permite să considerăm o valoare de un anumit tip ca fiind de alt tip. Aceasta se numește conversie de tip.

În C++ sunt două feluri de conversii de tip:

• conversia implicită
• conversia explicită

Conversia implicită

Conversia implicită intervine de la sine când într-o operație avem operanzi de tipuri diferite. Compilatorul consideră automat ambele date de același tip pentru a putea efectua operația.

Conversia implicită se face doar dacă operanzii sunt de tipuri compatibile – vezi mai jos o listă de compatibilități pentru tipurile numerice. Dacă tipurile nu sunt compatibile obținem eroare de sintaxă!

Exemple

Conversie de la int la double

#include <iostream>
using namespace std;

int main()
{
    int n = 5;
    double x;

    /// conversie de la int la double
    x = n;

    cout << "n = " << n << endl;
    cout << "x = " << x << endl;
	return 0;
}

n = 5
x = 5

Conversie de la double la int

#include <iostream>
using namespace std;

int main()
{
    int n;
    double x = 5.75;

    /// conversie de la double la int

    n = x;

    cout << "n = " << n << endl;
    cout << "x = " << x << endl;
	return 0;
}

n = 5
x = 5.75

Deoarece o dată de tip int memorează numere întregi, în timpul conversiei zecimalele valorii lui x s-au pierdut.

Pierderea de date în timpul conversiei

Așa cum am văzut în exemplul anterior, conversia de tip poate duce la pierderea (trunchierea) unor date. Acest lucru nu este neapărat rău, dar trebuie să fim conștienți de această situație.

În fapt, conversia este de două feluri:

• promovare – conversie de la un tip de date inferior la unul superior; nu produce pierdere de date!
• retrogradare – conversie de la un tip de date superior la unul inferior; poate produce pierdere de date!

În primul exemplu de mai sus a avut loc o promovare de la int la double, iar în al doilea exemplu a avut loc o retrogradare de la double la int. Cea de-a doua a condus la pierderea unor date.

În situațiile în care este posibil, compilatorul realizează conversiile implicite prin promovare.

De exemplu, rezultatul expresiei 2 + 1.5 va fi 3.5, nu 3. Are loc promovarea valorii 2 la tipul double, nu retrogradarea lui 1.5 la int, ceea ce ar fi însemnat pierderi de date!

Conversia explicită

Conversia explicită a datelor înseamnă modificarea manuală, de către programator, a tipurilor de date folosite într-o expresie. Se mai numește și type casting.

Operatorul de conversie explicită

Are sintaxa:

(TIP) expresie

sau

TIP(expresie)

Observații

• este un operator unar;
• are prioritate mare;
• rezultatul său este rezultatul expresiei, considerat de tipul de date TIP;
• în varianta a doua TIP trebuie să fie un nume de tip format dintr-un singur cuvânt. Astfel, expresia unsigned int(expresie) este greșită.

Exemplu

char c='A';
cout << (int) c << endl; // 65
cout << char(97) << endl; // a

Notă: Limbajul C++ oferă și următorii operatori de conversie: static_cast, dynamic_cast, const_cast și reinterpret_cast.

Câteva reguli privind conversia

• dacă se convertește un întreg negativ la un tip fără semn rezultatul va fi complementul în baza 2 a valorii inițiale, datorită modului de reprezentare a valorilor întregi. Astfel, -1 devine cea mai mare valoare a tipului fără semn, -2 devine a doua cea mai mare valoare, etc.
• la conversia unei valori numerice la tiplul bool rezultatul va fi:
  • true, dacă valoarea inițială este nenulă;
  • false, dacă valoarea inițială este 0;
• la conversia unei valori de tip float, double la un tip întreg, valoare se va trunchia, pierzându-se partea zecimală. Dacă rezultatul nu se încadrează în limitele tipului întreg, comportamentul programului devine impredictibil.

Regulile de mai sus se aplică atât pentru conversia implicită, cât și pentru cea explicită.

Exemplu: media aritmetică

Să presupunem că dorim să determinăm media aritmetică a trei numere întregi. Desigur, răspunsul este suma numerelor împărțită la 3, dar trebuie ținut cont de faptul că împărțirea a doi întregi este câtul împărțirii. Pentru a obține media corectă va trebui să facem anumite conversii.

Exemplu 1 – conversie implicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
/// cout << S / 3; // gresit - impartire intreaga
cout << S / 3.0;

A avut loc conversia implicită a lui S la double (promovare).

Exemplu 2 – conversie implicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
cout << 1.0 * S / 3;

A avut loc conversia implicită a lui S, apoi a lui 3, la double (promovări).

Exemplu 3 – conversie explicită

int a , b,  c;
cin >> a >> b >> c;
int S = a + b + c;
cout << (double)S / 3;

Mai întâi se convertește explicit valoarea lui S la double, apoi are loc conversia implicită la double a lui 3.

Evitarea depășirii de tip

În numeroase situații avem operații cu date de tip int, dar rezultatul depășește limita maximă (sau minimă) a acestui tip. Astfel se produce depășirea de tip – overflow. Soluția este utilizarea unor conversii prin care operațiile se realizează într-un tip de date mai larg, de exemplu long long.

Exemplu:

int n = 1000000;
cout << n * n << endl; /// posibil -727379968 - overflow
cout << 1LL * n * n << endl; /// corect 1000000000000
cout << (long long) n * n << endl; /// corect

La realizarea conversiilor trebuie ținut cont de precedența operatorilor. De exemplu, secvența de mai jos nu obține rezultatul corect.

int n = 1000000;
cout << 1LL * n + n * n << endl;
cout << (long long)n + n * n << endl;

Mai multe detalii despre conversii sunt diponibile aici: en.cppreference.com/w/cpp/language/implicit_conversion.

Definiție

Operatorul condițional este singurul operator ternar (cu trei operanzi) din C++. Sintaxa lui este:

ExpresieConditionala ? Expresie1 : Expresie2

și se evaluează astfel:

• se evaluează ExpresieConditionala. Rezultatul său va fi convertit implicit la bool.
• dacă rezultatul lui ExpresieConditionala este true, se evaluează Expresie1 și rezultatul său va fi rezultatul operației ?
• dacă rezultatul lui ExpresieConditionala este false, se evaluează Expresie2 și rezultatul său va fi rezultatul operației ?

Expresie2 și Expresie3 trebuie să aibă rezultate de același tip, sau de tipuri compatibile.

Exemplu

int x;
cin >> x;
cout << (x % 2 == 0? "par" : "impar");

Observații

• Operatorul ? poate fi înlocuit cu instrucțiunea if. Secvența de mai sus poate fi rescrisă astfel:
  

  int x;
  
  cin >> x;
  
  if (x % 2 == 0)
  	cout << “par”;
  
  else
  	cout << “impar”;

• Operațiile condiționale pot fi imbricate:
  

  cout << (x > 0? “pozitiv” : x == 0 ? “nul” : “negativ”);

• Rezultatele celor două expresii care reprezintă rezultatele posibile trebuie să fie de același tip sau de tipuri compatibile. Următoarea secvență nu este corectă;
  

  int x;
  
  cin >> x;
  
  cout << (x == 1? 1 : “diferit de 1”); // error: operands to ?: have different types ‘int’ and ‘const char*’

• Dacă expresiile Expresie1 și Expresie2 sunt de tip lvalue (de exemplu, variabile), rezultatul operației este chiar data corespunzătoare, nu valoarea ei, care poate fi apoi supusă unei atribuiri:
  

  int x = 1, y = 2, a = 10;
  
  ((a % 2 == 0) ? x : y) = 5;
  
  cout << x << “ “ << y << endl; // 5 2

Cea mai fecventă eroare este să uităm prioritatea operatorilor. Operatorul condițional are prioritate scăzută și este probabil să facem diverse erori!

În general, incrementarea unei date înseamnă mărirea valorii sale, de obicei cu 1, iar decrementarea unei date înseamnă micșorarea valorii sale.

Aceste operații sunt foarte frecvente. De aceea, numeroase limbaje de programare (inclusiv C/C++, Java, Javascript, C#, PHP) pun la dispoziția programatorilor operatori care fac tocmai acest lucru.

Operatorul de incrementare este ++, iar cel de decrementare este --. Sunt operatori unari și se pot aplica doar datelor (variabile sau operații care au rezultat de tip lvalue – element de tablou, câmp al unei structuri, etc.).

Operatorii de incrementare/decrementare nu se pot aplica pentru constante sau pentru operații care au ca rezultat valori (operații aritmetice, comparații, etc.).

De regulă, operatorii unari sunt prefixați (sunt plasați înaintea operandului, de exemplu - x). Operatorii de incrementare și decrementare pot fi atât prefixați ( se scriu înaintea operandului), cât și postfixați (se scriu după operand). Efectul lor este același (incrementarea/decrementarea operandului), dar rezultatul diferă.

Incrementarea

Operația de incrementare a variabilei X poate fi:

• postincrementare: X ++. Efectul expresiei este mărirea valorii lui X cu 1, iar rezultatul operației este valoarea inițială a lui X.
• preincrementare: ++ X. Efectul expresiei este mărirea valorii lui X cu 1, iar rezultatul operației este chiar variabila X (cu valoarea mărită, bineînțeles).

Exemplu postincrementare

int x = 5 , y = 10;
y = x ++; // y primeste valoare lui (x++), adica valoarea initiala a lui x
cout << x << " " << y; // 6 5

Exemplu preincrementare

int x = 5 , y = 10;
y = ++ x; // y primeste valoare lui (++x), adica valoarea marita a lui x
cout << x << " " << y; // 6 6

Observații

• preincrementarea are ca rezultat variabila (data) asupra căreia se aplică operația. În consecință, rezultatul poate fi folosit în orice context se poate folosi o lvalue – de exemplu i se poate aplica din nou operatorul de incrementare sau cel de decrementare.
• postincrementarea are ca rezultat o valoare – valoarea inițială a variabilei. Rezultatul postincrementării poate fi folosit doar în expresiile unde intervin valori.

Exemple:

int x = 5 , y = 10;
y = (++ x) ++; // x devine 7, y devine 6
cout << x << " " << y;

int x = 5 , y = 10;
y = ++ (x ++); // eroare, rezultatul lui x ++ nu este lvalue
cout << x << " " << y;

int x = 5 , y = 10;
y =  ++ ++ x; // x devine 7, y devine y
cout << x << " " << y;

Postincrementarea are prioritate mai mare decât preincrementarea (vezi aici prioritatea operatorilor). Din acest motiv următoarea secvență este greșită sintactic.

int x = 5 , y = 10;
y = ++ x ++; // eroare; prioritate are x ++, dar rezultatul sau nu este lvalue
cout << x << " " << y;

Decrementarea

Decrementarea respectă toate proprietățile incrementării, cu observația că valoarea datei asupra căreia se aplică se va micșora cu 1.

Operația de decrementare a variabilei X poate fi:

• postdecrementare: X --. Efectul expresiei este micșorarea valorii lui X cu 1, iar rezultatul operației este valoarea inițială a lui X.
• predecrementare: -- X. Efectul expresiei este micșorarea valorii lui X cu 1, iar rezultatul operației este chiar variabila X.