Jump to content

C valoda, mazākais kopigais dalāmais


Recommended Posts

Sveicināti, neesmu diez ko gudrs šajā jomā, bet man vajag izstrādāt programmu, lai atrod mazāko kopējo dalāmo skaitļiem N un M, ko ievada lietotājs. Kāds var ieskaidrot ar ko sākt?

 

 

p.s nedrīkst izmantot massīvu.

Edited by Llama
Link to post
Share on other sites

Sākt ar risinājuma izdomāšanu uz papīra.

Dalīšanas atlikums starp diviem skaitļiem C valodā  tiek iegūts, izmantojot "%" :

4 % 2 = 0

5 % 2 = 1

Edited by itanium
Link to post
Share on other sites

Kam tev masīvu?

 

Matemātikā par divu vai vairāk veselu skaitļu mazāko kopīgo dalāmo sauc mazāko naturālo skaitli, kas dalās ar katru no dotajiem skaitļiem bez atlikuma. Piemēram, skaitļu 6 un 15 mazākais kopīgais dalāmais ir MKD(6, 15) = 30, jo 30 dalās gan ar 6, gan 15, bet nav neviena mazāka naturāla skaitļa, kas ar tiem abiem dalītos.

Un atlikuma iegūšanai izmanto %

Edited by itanium
Link to post
Share on other sites

Un es tev saku, ka tev nemaz nevajag masīvu.

 

Ok, ok :

Sāc ar lielāko no diviem ievadītajiem skaitļiem.
Pieskaiti tam 1 un pārbaudi dalīšanas atlikumus ar ievadītajiem skaitļiem.
u.t.t.

 

Tiek ievadīti divi skaitļi : 3 un 5

Lielākais skaitlis = 5, 5+1=6

6 :

6/3 atlikums = 0

6/5 atlikums = 1

6+1=7

7 :

7/3 atlikums = 1

7/5 atlikums = 2

7+1=8

..

15 :

ČaČing

Edited by itanium
Link to post
Share on other sites
versatile

Bet masīvs nedrīskt būt programmā!!!!!111111one

 

Ja nopietni, tad skolas uzdevumiem šeit risinājumus priekšā neraksta, iedod tikai virzienu, kurā rakt. Tas jau ir izdarīts.

Ja neprot kaut ko konkrētu, raksti.

 

Pagaidām izdomā, kā problēmu risinātu uz papīra un tad uzraksti to programmā.

  • Patīk 1
Link to post
Share on other sites

Tomēr laikam nav jāsāk ar lielāko ievadīto skaitli +1, bet gan vienkārši ar lielāko ievadīto skaitli.

Ievadot 3 un 6, jāatgriež 6.

Edited by itanium
Link to post
Share on other sites

 

#include <stdio.h>

#include <conio.h>

*/

void main() {

    int n,m,x,i,r;

    do

    {

        printf("Ievadiet Skaitli N un M\n");

        scanf("%d%d",&n, &m);

        if(n>m)

            x=n;

        else

            x=m;

 

            for(i=x;i>=1;i--){ 

                if(n%i==0&&m%i==0){

                    printf("Mazakais kopigais dalamais : %d \n",i) ;

                    getch();

            //break;

         }

    }

    }

    while (x==1);

 

 

    getch();

}

 

Link to post
Share on other sites

 

 

Kam tev masīvu?

Sēdies, 2

 

Lai atrastu LCM, GCD utt, var izmantot skaitļlu sadalīšanu pirmreizinātājos. Šos "derīgos" pirmreizinātājus kaut kur tak ir jāglabā - masīvā. Ja skaitļi ir ierobežoti, tad masīvs var noderēt arī visu iespējamo pirmskaitļu uzglabāšanai, lai atvieglotu dalīšanu. Ja neko nejaucu, tad jebkura unsigned 32bit skaitļa sadalīšanai pirmreizinātājos pietiek ar 6542 skaitļu masīvu. Pat pitonā tāda 32bit skaitļa sadalīšana pirmreizinātājos nostrādā sekundes tūkstošdaļās.

 

Es gan nesaprotu, kāpēc nedrīkst izmantot masīvu… Vai nu studentus uzskata par pilnīgiem pamuļķiem (t.i., pieņem, ka meklēs internetā, bet tur visi piemēri būs ar masīvu izmantošanu, līdz ar to masīva izmantošana liecinātu par to, ka students nav pats izdomājis risinājumu), vai tieši otrādi - par ģēnijiem. Kā tur ir, ir kaut kāda iespēja uzrakstīt efektīvu LCM algoritmu, kas neizmantotu masīvus?

Link to post
Share on other sites

 

 

r kaut kāda iespēja uzrakstīt efektīvu LCM algoritmu, kas neizmantotu masīvus?
 

 

tur nevajag nekādus masīvus

Link to post
Share on other sites


module Main where

   

lkd a b | b == 0 = a

        | otherwise = lkd b (mod a b)

 

 

mkd a b = a * b `quot` lkd a b

    

-- | es uzrakstīju vēl vienu programmu,  kāds vēlas to uzkodēt iekš ASM  x64 ?  LOL

main :: IO ()

main = print $ mkd 5 6

Link to post
Share on other sites

/** DjSteins algoritms, remix by DjUbuntu <C> 2012, b00t.lv */ 

#include <stdio.h>
#include <conio.h>

 

unsigned int gcd(unsigned int u, unsigned int v)
{
if (u == v)
return u;

if (u == 0)
return v;

if (v == 0)
return u;

// look for factors of 2
if (~u & 1) // u is even
{
if (v & 1) // v is odd
return gcd(u >> 1, v);
else // both u and v are even
return gcd(u >> 1, v >> 1) << 1;
}

if (~v & 1) // u is odd, v is even
return gcd(u, v >> 1);

// reduce larger argument
if (u > v)
return gcd((u - v) >> 1, v);

return gcd((v - u) >> 1, u);
}

int main(void){ 
   unsigned int m,n,rezultats;
 
        printf("Ievadiet Skaitli N un M\n");
        scanf("%d%d",&n, &m);
   rezultats = gcd(m, n);
   printf("laaciitis saka %d \n", n);
   return 1; 
}
 

 

 

tātad pamatskolā nemācījos gramatiku un tāpēc šādi ķēmojos kaut kaa shitaa, vieniigi man nav c epilatora, jo mamma aizliedza instaleet speeles, liidz nebuushu sekmiigs sportaa. 

Link to post
Share on other sites
;; vēl daži varianti, kā to var uzkodēt LOL

(defn lcm2 [a b] 
  (letfn [(gcd [a b] (cond 
                      (zero? b) a 
                      :else (recur b (mod a b))))]
    (/ (* a b) (gcd a b))))


(defn lcm3 [a b] 
  (letfn [(gcd [a b] (case b 
                       0 a 
                       (recur b (mod a b))))]
    (-> (* a b) (/ (gcd a b)))))


(defn lcm4 [a b] 
  (letfn [(gcd [a b] (condp = b 
                       0 a 
                       (recur b (mod a b))))]
    (->> (gcd a b) (/ (* a b)))))


(defn lcm5 [a b] 
  (let [gcd (fn [a b] (condp #(= %1 (zero? %2)) b 
                        true a 
                        false (recur b (mod a b))))]
    (/ (* a b) (gcd a b))))


(defn lcm6 [a b] 
  (letfn [(gcd [a b] (condp get b 
                       #{0} :>> (partial + a) 
                       (recur b (mod a b))))]
    (/ (* a b) (gcd a b))))

(defn lcm7 [a b] 
  (letfn [(gcd [a b] (cond
                      (zero? a) b
                      (zero? b) a
                      (= a b) a
                      (even? a) (if (even? b) (* 2 (gcd (bit-shift-right a 1) (bit-shift-right b 1))) (gcd (bit-shift-right a 1) b))
                      (and (odd? a) (even? b)) (gcd a (bit-shift-right b 1))
                      (and (odd? a) (odd? b)) (if (< a b) (gcd (bit-shift-right (- b a) 1) a) (gcd (bit-shift-right (- a b) 1) b))))]
    (/ (* a b) (gcd a b))))

 

(defn lcm8 [a b]
  (letfn [(first-eq [[x & xt :as xs] [y & yt :as ys]]
            (cond (= x y) x
                  (> x y) (recur xs yt)
                  :else (recur xt ys)))
          (plus-seq [a] (iterate (partial + a) a))]
    (apply first-eq (map plus-seq [a b]))))
Edited by MarisO
Link to post
Share on other sites
Lai atrastu LCM, GCD utt, var izmantot skaitļlu sadalīšanu pirmreizinātājos. Šos "derīgos" pirmreizinātājus kaut kur tak ir jāglabā - masīvā. Ja skaitļi ir ierobežoti, tad masīvs var noderēt arī visu iespējamo pirmskaitļu uzglabāšanai, lai atvieglotu dalīšanu.

Sēdies, 1

 

Ja prasība ir bez masīva, tad ir jātaisa bez masīva. Un šo uzdevumu var izpildīt, neizmantojot masīvus!

Viens no iemesliem tam varētu būt tāds, ka studenti vēl nemaz nav apguvuši masīvus, bet labāk to vienkārši uzskatīt par brain teaseri (visai tizlu gan).

 

Un vēl joprojām :

izmantojam Eiklīda algoritmu

dalāmais != dalītājs, kā arī lielākais != mazākais

Bērniem

Edited by itanium
Link to post
Share on other sites

Nu ja prasība ir, tad tai jābūt pamatotai, prētējā gadījumā tas ir bezjēdzīgs ierobežojums, kas kavē gan izaugsmi, gan izpausmi, gan izdomu - faktiski visu labo. Uz jautājumu "kam tev masīvu?" atbildēt "tāpēc, ka skolotāja tā teica" arī ir kaut kās stulbi.

 

Iet cauri visiem skaitļiem (#6) būtu knapu 4 baļļu vērta atbilde. OK, 3 baļļu - pēc #9 varētu pacelt uz 4 ballēm.

 

Ar Eiklīda algoritma noniecināšanu, sakot "dalāmais != dalītājs, kā arī lielākais != mazākais", iebrauci auzās - Eiklīda algoritms kā reiz ir viens no algoritmiem, kas noder LCM aprēķināšanai (daudz efektīvākai nekā #6 postā aprakstītais algoritms):

5b3f3c62dd59cc5594af7b2ece3798fb.png

Link to post
Share on other sites
Iet cauri visiem skaitļiem (#6) būtu knapu 4 baļļu vērta atbilde. OK, 3 baļļu - pēc #9 varētu pacelt uz 4 ballēm.

Saderam, ka vairāk? (20€)

Lai autors izlabo savu skritcelējumu, nodod, dabūn atzīmi un pēc tam ieraksta to te.

1. kursa studentiem nav īpaši jādomā par optimizāciju.

+ ja šie algoritmi nav mācīti (nezinu vai ir), tad cerēt, ka students tos pats izdomās ir visai naivi.

 

Ja šie algoritmi lekcijās tomēr tika apspriesti, bet autors to nogulēja, tad gan atvainojos.

 

iebrauci auzās

Nu, nu. Man un citiem biedriem nav jāzīlē, ko cilvēks ar vienu vārdu ir domājis.

Eiklīda algoritms ir paredzēts lielākā kopējā dalītāja atrašanai (punkts)

Edited by itanium
Link to post
Share on other sites

Man un citiem biedriem nav jāzīlē, ko cilvēks ar vienu vārdu ir domājis.

Takš seko diskusijai, nevis lasi postus ārpus konteksta! Citādi ne to vien atradīsi.
Link to post
Share on other sites

Derēt vari ar sienu. Sen zināms, ka universitātes aiz ausīm velk studentus pa konveijeri, nevis liek mācīties, domāt un darīt. Tas arī atzīmēs atspoguļojas - it kā skolā izcilnieks, bet ārpus skolas reti kurš spēj ko vairāk par "hello, world" uzrakstīt. Tā ka pat ja cilvēkam par "for (int i = max(a, b); true; i++) {...}" iedos 9 balles, tas nenozīmē, ka tāds algoritms būtu vairāk kā 4 baļļu vērts.

Jāzīlē nav, bet pietiek kaut vai wiki par LCM atvērt, lai ieraudzītu milzīgu formulu, kurā izmantots GCD, kuru, savukārt, var aprēķināt ar minēto Eiklīda algoritmu. Tur pat nav jālasa "smalko druku", lai to pamanītu/saprastu.

Edited by binary
Link to post
Share on other sites

Jā, to MarisO jau 2h pirms tā posta te uzrakstīja...

 

Par izglītības sistēmu labāk kādā citā tēmā. Bet

 

 

nevis liek mācīties, domāt un darīt.

Ja tev jau gatava algoritma pārvēršana programmā liekas domāt veicinošāka, nekā izdomāt savu risinājumu (kaut lēnāku), tad tu esi tāds pats kā 90% no RTU pasniedzējiem.

Edited by itanium
Link to post
Share on other sites

Tatad gala rezultats, ieguvu 9.

#include <stdio.h>
#include <conio.h>
int main()
{
int n, m, x;  //Lietotaja ievadities skaitli un mazakais kopejais dalamais
char r;
	do
	{
		printf("Ievadi 2 pozitivus skaitlus: ");
		scanf("%d %d", &n, &m);
		if (n > 0 && m > 0) //Parbauda, vai nav vienads vai mazaks ar nulli)
			{
			x=(n>m) ? n : m; /* Maksimala vertiba tiek glabata x vertiba */
			while(1)                       /* Vienmer paties. */
			{
				if(x%n==0 && x%m==0)
				{
					printf("Mazakais kopejais dalamais no skaitliem  %d un %d ir: %d\n", n, m, x); //Izvada rezultatu
					break;          /* Aptur ciklu. */
				}
				++x;
			}
		}
		else printf("N un M nevar but mazaks vienads par 0\n");

			printf("Ievadi J lai atkartotu, lai beigtu N\n");//Piedava atkartot programmu
			scanf("%s", &r);
			system("cls");
	}
  while ( r == 'j' || r == 'J' );//Atkarto programu
}

Link to post
Share on other sites

 

 

Ja tev jau gatava algoritma pārvēršana programmā liekas domāt veicinošāka, nekā izdomāt savu risinājumu (kaut lēnāku), tad tu esi tāds pats kā 90% no RTU pasniedzējiem.

Zini, tas cikls, kas beztolkā iet cauri visiem iespējamajiem skaitļiem, nav "sava risinājuma izdomāšana" - tas ir pirmais acīmredzamais algoritms. Tur pat domāt nevajag, lai tādu "izdomātu". Tādā ziņā gatavā Eiklīda algoritma sasaistīšana ar LCM aprēķināšanu prasa daudz vairāk domāšanas ;)

 

Autoram - ko lai saka, apsveicu ar labu atzīmi… ;)

Link to post
Share on other sites

Jā, zinu… A ko padarīs - 9 par tādu liek, tātad nav jēgas domāt ko jēdzīgāku (da kaut vai "while (1)" aizvietot ar "while (x % n || x % m)", pat tas būtu par kripatu labāk). Posts #26 paliek spēkā :D

Edited by binary
Link to post
Share on other sites

 

 

Tādā ziņā gatavā Eiklīda algoritma sasaistīšana ar LCM aprēķināšanu prasa daudz vairāk domāšanas ;)

Bet, protams, Wiki apskatīties formulu ir sarežģītāk...


 

 

Zini, tas cikls, kas beztolkā iet cauri visiem iespējamajiem skaitļiem, nav "sava risinājuma izdomāšana" - tas ir pirmais acīmredzamais algoritms

Nezinu! Laikam jau visiem nemaz tik acīmredzams nav, ja jau tika tāda tēma izveidota.

Link to post
Share on other sites

Protams. Ir taču atšķirība starp uzdevuma izlasīšanu un elementāra cikla uzrakstīšanu (kas šoreiz ir gala risinājums) UN uzdevuma izlasīšanu, wiki atvēršanu, formulu apskatīšanos, iepazīšanos ar algoritmu un algoritma implementēšanu kodā. Tas tiešām ir mazliet sarežģītāk. Turklāt, ja algoritms nav zināms, tad arī jaunas lietas var iemācīties.

 

Tā tīri intereses pēc - cik ilgā laikā tas kods atradīs LCM priekš 89248 un 91176 (rezultāts ir 1017159456)? Kādas 5 sekundes būs?

Link to post
Share on other sites

Piekrītu tev, ka iepazīšanās ar jauniem algoritmiem par skādi nenāks, bet tik primitīvām lietām var arī pats "izdomāt".

 

Par ātrdarbību nemācēšu pateikt - ne tam šajā gadījumā ir nozīme, ne man ir kur to pārbaudīt, ne es esmu programmētājs

http://www.compileonline.com/compile_c_online.php - pie tādiem skaitļiem pakaras ;)

 

P.S. Vilx-, kāpēc apstājās prog.21.lv?

Edited by itanium
Link to post
Share on other sites

Redz, nokarās… Tas vien jau liecina par to, ka lieta nav nemaz tik primitīva. C kods ar tiem skaitļiem tiešām izpildās ~5 sekundes. Pitona trīsrindīte ar Eiklīda algoritma izmantošanu - 0.0005 sekundes (10'000x ātrāk!), atbilstošs C kods - vēl par dažām kārtām ātrāk. Ar to "a * b / gcd(a, b)" variantu gan varētu būt neliela problēma. Konkrētāk - problēma varētu būt ar "a * b" daļu. Lai no tās izvairītos, vajadzētu ierobežot a un b max vērtības (to gan arī "tupa cikla" gadījumā vajadzētu darīt). Tiesa, tādas lietas laikam skolā nemāca…

Edited by binary
Link to post
Share on other sites

Visu diemžēl nevar iemācīt.

Autors visticamāk ir pirmā kursa students, un man ir aizdomas, ka šajā gadījumā uz uzdevuma nodošanas brīdi pat masīvs bija out of scope (nebija vēl mācīts), tāpēc arī varētu būt tādas prasības.

Un pirmkursniekiem liekas, ka par performanci vispār neko nemāca.

 

Par to algoritmu tēma, manuprāt, izsmelta.

Ne es MarisO doto variantu noliku, ne es esmu teicis, ka mans variants ir labākais.

Vien to, ka pliks Eiklīda algoritms tam nav paredzēts, kā arī to, ka masīvi rezultāta ieguvei nav viennozīmīgi nepieciešami.

 

Ja jau autors par šo dabūja 9, značit pasniedzējs dabūja to, ko vēlējās.

Edited by itanium
Link to post
Share on other sites

To prasību vienalga nesaprotu. Pat ja nebija mācīts - so what? Pasniedzējam kompleksi varētu rasties, uzzinot, ka 1. kursa students varētu zināt (vai vismaz gribēt apgūt) ko vairāk nekā pasniedzējs uz tāfeles uzrakstījis? Pasniedzējam bail, ka varētu nesaprast, kāpēc uzrakstītais kods strādā? Manuprāt, ja students mājas darbā ietver kaut ko, kas nav mācīts - tas ir tikai apsveicami. Un tam būtu jābūt vienīgajam veidam, kā var nopelnīt (tiešām nopelnīt, nevis vienkārši dabūt) ko vairāk par 6-8 ballēm.

Link to post
Share on other sites

Šaubos, ka kompleksi vai bailes.

Vienkārši ir mācīts tas, kas ir mācīts, un ar to arī jāiztiek.

Ne viņiem ir laika, ne vēlme katra studenta darbam iet cauri rindu pa rindai

+ vēl pārjautāt, vai pats students saprot to, ko tur ir sarakstījis.

 

Šis vispār ir jājautā pasniedzējiem, nevis man.

Zinu tik to (pēc paša pieredzes par līdzīgiem jautājumiem), ka viņiem nepārāk patīk "dumpinieki" :D

Edited by itanium
Link to post
Share on other sites
C kods ar tiem skaitļiem tiešām izpildās ~5 sekundes

 

 

ta jau mana programma ir ātrāka  labāka

sandbox.lcm> (time  (lcm 89248  91176))  ;; Eiklīds
"Elapsed time: 0.09 msecs"
1017159456
sandbox.lcm> (time  (lcm7 89248  91176))  ;; Binārais algoritms
"Elapsed time: 0.221 msecs"
1017159456
sandbox.lcm> (time  (lcm8 89248  91176))  ;; optimizēta pilnā pārlase
"Elapsed time: 52.717 msecs"
1017159456

īstenībā es esmu pārsteigts, ka studentiem liek rakstīt šādas draņķīgas programmas , kad es studēju, tad šādas lietas netiktu atbalstītas

Edited by MarisO
Link to post
Share on other sites

MarisO, labāka nekā pilnā pārlase - jā, varbūt. Lai gan nestādos priekšā, kādas tev tur optimizācijas. Eiklīds gan tev pašvaks. C man uz 6+ gadus vecā laptopa 4'000'000'000 iterācijas sarēķina 4.3 sekundēs, tātad 1 iterācija ir 0.000001 msecs.
 

unsigned int gcd(unsigned int a, unsigned int b)
{
    return a == b ? a : gcd(min(a, b), max(a, b) - min(a, b));
}

unsigned int lcm(unsigned int a, unsigned int b)
{
    return a / gcd(a, b) * b;
}
lcm() darbību secību nācās pamainīt ;) Tā teikt, "mazliet padomāt", nevis brutāli implementēt wiki atrastu formulu. Uzminiet nu, kāpēc tā ;) Edited by binary
Link to post
Share on other sites

Labrīt, LU DF pirmajā kursā, ja apmeklē pareizo grupu un negrib ripināt gurķi elementārajās grupās, tad pasniedzēji arī runā par algoritmu ātrdarbību, atmiņas/laika lietām. 

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
×
×
  • Create New...