Baxtli chipta yohud Avtobusda ham matematika!

Ko`pincha avtobusga chiqqanimda qo`limga konduktor chipta berib ketadi...Shu chiptani olayotgan paytimda sekin raqamlariga qarayman, agar baxtli chiqib qolsa bormi xursand bo`lib o`zimga o`zim kuch bag`ishlayman.
Shunday qilib men sizlarga 8 xonalik sonlar ichida shu omadli chipta necha kishini xursand qilar ekan deb ularni C/C++ tilida sanab chiqdim…

Dasturlashni endi o`rganayotganlarning aksariyatini aytmaganda ko`pchiligi acm.timus.ru saytiga kirmaganlari bo`lmasa kerak. Men «OPPENNET»da ushbu saytdagi yohud avtobusdagi meni xursand qiladigan chiptalar uchun o`ylab topilgan masalani ishlab ko`rsatmoqchiman.

Omadli chipta

Avvalo o`zgaruvchilarni e`lon qilib olamiz.

int n,RemNumber,LTicket=0;
int t=0,count;

n => " Necha xonalik sonlar"
n=2 bo`lsa, demak 99, n=3 bo`lsa, demak 999 va hakozo…

So`ngra chipta omadli yoki omadsiz ekanligini tekshirish uchun bizning chipta juft xonali bo`lishi kerak bo`ladi.
shu sababdan juft xonali ekanligini tekshiramiz:

if(n%2==0) {
                 switch(n)
                          {
                            case 2:
                                 count = 99;
                                 break;
                            case 4:
                                 count = 9999;
                                 break;
                            case 6:
                                 count = 999999;
                                 break;
                            case 8:
                                 count = 99999999;
                                 break;
                            default:
                                 cout<<"faqat 6 xonali sonlar uchun!";
                                 break;
                         }   
                 }
    else cout<<"F4q4t juft sonlar kiritilsin! (axir bilet raqamlari soni toq bo`lmaydiku :)";

Keyingi qadamda biz siklda o`zlashtirilgan har bir sonni bir o`zgaruvchiga tenglab uni raqamlarini massivga yig`ib boramiz va massivning har bir indeks ostidagi raqamlardan foydalanib chipta sonini ikki bo`lakka ajratib olamiz hamda bo`laklardagi raqamlarni qo`shib ularni teng yoki teng emasligini tekshiramiz.Agar teng bo`lsa demak chiptamiz omadli :) va shu omadli chiptani sanab boramiz…

for( int i = 0; i <= count; i++)
        {
             RemNumber = i;
             t=0;
             do{
                     // RemNumber 236902 teng bo`lsin
                     t++;
                     a[t]=RemNumber%10; //qoldiqni hisoblaydi 236902 >>> 2 
                     RemNumber=RemNumber/10; // butun qismni o`zlashtiradi >>> 23690
             }
             while(RemNumber>0);
             
             if(n==2 && a[1] ==a[2]) LTicket++; 
             if(n==4 && a[1] + a[2] ==a[3] + a[4])LTicket++; 
             if(n==6 && a[1] + a[2] + a[3] ==a[4] + a[5] + a[6]) LTicket++;
             if(n==8 && a[1] + a[2] + a[3] + a[4] ==a[5] + a[6] + a[7] + a[8]) LTicket++;                
        }

Dastur to`liq kodi:

#include <iostream>
#include <cmath>
long int a[99999999];
using namespace std;
int main()
{
    int n,RemNumber,LTicket=0;
    int t=0,count;
    cin>>n;
    if(n%2==0) {
                 switch(n)
                          {
                            case 2:
                                 count = 99;
                                 break;
                            case 4:
                                 count = 9999;
                                 break;
                            case 6:
                                 count = 999999;
                                 break;
                            case 8:
                                 count = 99999999;
                                 break;
                            default:
                                 cout<<"faqat 6 xonali sonlar uchun!";
                                 break;
                         }   
                 }
    else cout<<"F4q4t juft sonlar kiritilsin! (axir bilet sonlar soni toq bo`lmaydiku :)";
    for( int i = 0; i <= count; i++)
        {
             RemNumber = i;
             t=0;
             do{
                     // RemNumber 236902 teng bo`lsin
                     t++;
                     a[t]=RemNumber%10; //qoldiqni hisoblaydi 236902 >>> 2 
                     RemNumber=RemNumber/10; // butun qismni o`zlashtiradi >>> 23690
             }
             while(RemNumber>0);
             
             if(n==2 && a[1] ==a[2]) LTicket++; 
             if(n==4 && a[1] + a[2] ==a[3] + a[4])LTicket++; 
             if(n==6 && a[1] + a[2] + a[3] ==a[4] + a[5] + a[6]) LTicket++;
             if(n==8 && a[1] + a[2] + a[3] + a[4] ==a[5] + a[6] + a[7] + a[8]) LTicket++;                
        }
        cout << "Omadli chiptalar soni: " << LTicket << endl; 
    system("pause");
    return 0;
}

Maqolam so`ngida shuni aytmoqchi edimki ushbu masalani har xil usulda ishlash mumkin, men esa boshlovchi dasturchilarga yordam bo`lsin deb batafsilroq yozishga harakat qildim)))
, ,

8 комментариев

boburiy
RAhmat. Kecha twitterda o'qigan bir anekdot esimga tushib ketti bu maqolangizdan so'ng. :)
-O'rtoq doim menga konduktor bilet berganida chiroyli-chiroyli raqam tushadi menga. Omadli bo'lsam kerakda-a?
-Omadli? Omadli bo'lganingda avtobusda yurarmiding
0
AlisheR1990
Piyoda yurgan odam uchun avtobusda ketayotgan inson omadli! :)
0
U2B3K
haqiqiy «bruteforce» yechim ekan :)
Bu yechimda 8 xonalilarni xisoblashda dastur uzoqroq o'ylansa kerak.
Va nimaga a massiv shunchaki int a[9];
emas?
0
sultonsanjar
Mana buni ham tekshirib ko`ring, massiv ham, case ham shart emas!
#include <iostream>
#include <math.h>
using namespace std;
int main()
    {
          int n,s,a1,a2,count;
          cin>>n;
          if(n%2==1&&n>0)
            cout<<"TOQ";
          else
			{
				count=pow(10,n)-1;
				for(int i=1;i<=count;i++)
				{
					s=i;
					int j;
					a1=a2=j=0;
					while(s>0)
					{
						j++;
						if(j<(n/2+1))
							a1+=s%10;
						else
							a2+=s%10;
						s/=10;
					}
					if(a1==a2)
						cout<<i<<endl;
				}
				
			}
          system("pause"); 
   }
0
U2B3K
agar dinamik dasturlashni hisobga olmay faqat pereborni ko'radigan bo'lsak, xomaki variant:
n=xonalar soni, q=pow(10,n/2)
sikl (s1=1; s1<q; s1++)
sikl (s2=i; s2<q; s2+=9)
agar sumraqam(s1)=sumraqam(s2) bo'lsa, natija++

agar xato bo'lmasa iterasiyalar soni 9marta kamayadi, ~10 marta tezroq natija olinadi.
0
AlisheR1990
man shunchaki tushunarli bo`lishi uchun yozgandim)))

int main()
    {
     int N;
     scanf("%d", &N);
     switch(N)
     {
      case 2: printf("10\n"); return 0;
      case 4: printf("670\n"); return 0;
      case 6: printf("55252\n"); return 0;
      case 8: printf("4816030\n"); return 0;
      default: return 0;
     }
     return 0;
0
AlisheR1990 

#include <iostream>
using namespace std;
int pow(int x, int n);
int sum(int n);
int main() {
    int num;
    int lucky = 0;
    cin >> num;
    for(int l=0;l<=(pow(10,num/2)-1);l++) {
        for(int r=0;r<=(pow(10,num/2)-1)/2;r++) {
            if(sum(l)==sum®) lucky++;
        }
    };
    cout << lucky*2 << "\n";
    return 0;
}

int pow(int x,int n) {
    int y=1;
    for(int i=0;i<n;i++) {
        y*=x;
    }
    return y;
}

int sum(int n) {
    int k=0;
    int it=1;
    do {
        k+=n%10;
        n/=10;
    } while (n>=1);
    return k;
}


Agar sizni fikrizni tushungan bo`lsam shuni nazarda tutdiz, bu dastur 1.5↑2 sek ishlaydi, shunda ikkita O(n/2) takrorlanish vaqtini qisqartirgan bo`lamiz…
0
U2B3K
yo'q buni nazarda tutmadim, mana bunday (C#):

public int Calc(int n)
{
    int result=1, sum1, sum2;
    int iter=(int)Math.Pow(10,n/2);
    for (int i = 1; i < iter; i++)
    {
	sum1=SumDigits(i);
        for (int j=sum1; j<iter; j+=9)
	{
		sum2=SumDigits(j);
		if (sum1==sum2) result++;
	}

    }
    return result;
}

int SumDigits(int num)
{
    int sum = 0;
    do
    {
        sum += num % 10;
        num /= 10;
    } while (num > 0);
    return sum;
}


Mana qiziqishga qilgan yuzaki test natijalarim:
2 xonalilar uchun 10000 marta, 4 xonalilar uchun 100 marta, 6 va 8 xonalilar uchun 1 marta bajarilgandagi shartli vaqtlar miqdori
			2 xona		4 xona		6 xona		8 xona
U2B3K	        :	16		16		17		2600
Alisher1990 (v2):	86		130		200		21912
sultonsanjar	:	95		175		340		37506
Alisher1990 (v1):	110		190		344		38125

Aslida bu misolni to'g'ri optimal yechimi juda qisqa vaqtlarda bajariladi
1