Бақытты санның кодтық шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма
Хэш

Проблемалық мәлімдеме

Мәселе санның бақытты нөмір екенін немесе жоқтығын тексеруде.

Бір сан бақытты дейді нөмір егер санды оның цифрларының квадраттарының қосындысымен алмастырса және процесті қайталау болса, бұл санды 1-ге тең етеді, егер ол 1-ге айналмаса және 1-ге кірмейтін циклде шексіз айналса, бұл бақытты_сан емес.

мысал

19
true

Түсіндіру:

Бақытты нөмір

1 ^ 2 + 9 ^ 2 = 82
8 ^ 2 + 2 ^ 2 = 68
6 ^ 2 + 8 ^ 2 = 100
1 ^ 2 + 0 ^ 2 + 0 ^ 2 = 1 (Бақытты нөмір)

2
false

Түсіндіру:

Қайта 4 санына жеткендіктен, ол тізбекте мәңгі айналады және ешқашан 1-ге аяқталмайды. Демек, берілген сан бақытты сан емес.

жақындау

Біз уақыт циклінде қайталай аламыз және санды 1-ге айналғанға дейін оның цифрларының квадраттарының қосындысымен ауыстыра аламыз, егер әрбір жаңа түрлендірілген сан бұрын болмауы керек болса, әйтпесе біз анықталмаған циклге ауысамыз.
Ол үшін алдымен бүтін сандар жиынын алып, келесі әрекеттерді орындай аламыз:

  1. Егер ағымдық сан орнатылған return-да бар болса (цикл табылды).
  2. Егер ол 1-ге тең болса, ол қайтып келеді
  3. Басқасы ағымдағы санды жиынға енгізіп, ағымдағы санды оның цифрларының квадратының қосындысымен алмастырады.
  4. Сол процесті қайталаңыз.

Іске асыру

C ++ санының бақытты санының шешім кодына арналған бағдарламасы

#include <bits/stdc++.h>
using namespace std;

bool isHappy(int n) {
                 
    set<int> s;

    while(s.count(n)==0)
    {
        if(n==1) return true;
        s.insert(n);
        int temp=0;

        while(n)
        {
            temp+= (n%10)*(n%10);
            n/=10;
        }
        n=temp;
    }
    return false;
}

int main()
{ 
    int n=19;
    
    if(isHappy(n)) 
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
 return 0;
}
true

Бақытты санның кодтық шешіміне арналған Java бағдарламасы

import java.util.*;
import java.lang.*;

class Happy
{  
     public static boolean isHappy(int n) 
     {
        
        Set<Integer> set = new HashSet<Integer>();
        int sum,digit;

        while (set.add(n)) 
        {
            sum = 0;
            while (n > 0) {
                digit = n%10;
                sum += digit*digit;
                n /= 10;
            }
            if (sum == 1)
                return true;
            else
                n = sum;

        }
        return false;
    }
    
    
    public static void main(String args[])
    {
       int n=19;
       System.out.println(isHappy(n));
    }
}
true

Сандық кодтың бақытты шешімі үшін кешенділікті талдау

Уақыттың күрделілігі

O (logn):  Мұндағы n - берілген сан. Тізбектегі санның әрбір цифрының квадратының қосындысын табу құны log (n) құрайды, ал логарифмдік коэффициентпен сан азая береді. Демек күрделілік = O (logn) + O (loglogn) + O (logloglogn) +….
Мұнда O (log⁡n) - басым бөлігі. Демек, жалпы күрделілік O (logn) құрайды.

Ғарыштың күрделілігі 

O (logn):  Жиынтықтың максималды өлшемі берілген санмен уақыттың күрделілігі сияқты логарифмдік болады.