Clasa a VI-a lecția 23 - 5 mar 2015

Tema - rezolvări

Rezolvări aici [1]

Tema - comentarii

Problema prieteni 1

Cum nu se scrie căutarea unui element în vector:

for (i1=0;i1<n;i1++){
  if (v[i1]==p){
    exista=1;
    break;
  }
}

Problema număr 2

La problema număr 2 nu este nevoie să memoraţi numerele într-un vector. Băban, Fares, şi alţii.

• Băban: n-ai folosit vector de frecvenţă. De ce?
• Piţur: suma nu are cum să fie zero, (problema nu spune clar). AVem formulă pentru cifra de control.

Problema alarma

Atenţie: pentru abs() trebuie să includeţi <stdlib.h>. Ţineţi minte afişarea folosind fprint() şi "%02d", mulţi v-aţi complicat înfiorător la afişare.

• Muşat: ai declarat vectorii de cifre de 9 elemente. Avem 10 cifre (altfel s-ar numi sistemul noual, nu zecimal).
• Cioltan: te complici la citire, te complici la afişare, algoritmul este complicat. Trebuie să cauţi cele mai simple soluţii.
• Dumitriu: frate cu Cioltan? Aceleaşi observaţii.
• Ichim: sursa nu este C. Eu vorbesc, eu aud. Include <stdio.h> si <stdlib.h>.
• Fares: ce-i complicaţia aceea? Scrie cît mai simplu.
• Georgescu: calculezi min=(1<<30)-1+(1<<30). Nu te complica cu ce nu cunoşti bine. Apoi algoritmul este incorect, bazat pe cifre, nu pe ore si minute. Cod mult şi greşit.

Problema ecuaţie 2

Există o instrucţiune magică: se cheamă switch. Bravo Nanu (interesantă rezolvare) şi alţii care aţi folosit-o.

Lecție

Calculul multiplicității unui număr prim în n!

Matematicianul Adrien-Marie_Legendre a descoperit că multiplicitatea (exponentul) unui număr prim p care apare în descompunerea în factori primi a lui n! poate fi exprimată exact ca:

$Exp(p,n!)=\left\lfloor {\frac {n}{p}}\right\rfloor +\left\lfloor {\frac {n}{p^{2}}}\right\rfloor +\left\lfloor {\frac {n}{p^{3}}}\right\rfloor +\cdots =\sum _{i=1}^{\infty }\left\lfloor {\frac {n}{p^{i}}}\right\rfloor .$

Acest fapt se bazează pe numărarea factorilor p ai întregilor de la 1 la n. Numărul multiplilor lui p în numerele de la 1 la n este $\textstyle \left\lfloor {\frac {n}{p}}\right\rfloor$; dar această formulă numără numerele cu doi factori p o singură dată. De aceea trebuie să mai numărăm încă $\textstyle \left\lfloor {\frac {n}{p^{2}}}\right\rfloor$ factori ai lui p. În mod similar pentru trei, patru, cinci factori, pînă la infinit. Însă suma este finită deoarece p ⁱ este mai mic sau egal cu n într-un număr finit de valori ale lui i, drept care funcția parte întreagă va fi zero pentru toate celelalte valori.

Cînd scriem programul pentru calculul exponentului ne vom opri la acel i pentru care pⁱ > n.

Calculul multiplicității unui număr prim la o putere în n!

Este simplu de demonstrat că dacă avem un număr prim p la o putere k atunci multiplicitatea lui p^k în n! este

$Exp(p^{k},n!)={\frac {Exp(p,n!)}{k}}$

Calculul multiplicității unui număr oarecare în n!

Este simplu să arătăm că dacă avem un număr a a cărui descompunere în factori primi este

a = p₁^k₁ • p₂^k₂ • … • p_m^k_m

atunci multiplicitatea (exponentul) lui a în n! este

$Exp(a,n!)=min(Exp(p_{1}^{k_{1}},n!),Exp(p_{2}^{k_{2}},n!),\ldots ,Exp(p_{m}^{k_{m}},n!))$

sau

$Exp(a,n!)=min({\frac {Exp(p_{1},n!)}{k_{1}}},{\frac {Exp(p_{2},n!)}{k_{2}}},\ldots ,{\frac {Exp(p_{m},n!)}{k_{m}}})$

Temă

Tema 23 clasa a 6^a

• factk .campion 2004
• fact ONI 2006 clasa a 9^a
• trei divizori

Rezolvări aici: [2]