අංකයක් ශුන්‍ය ලීට්කෝඩ් විසඳුම දක්වා අඩු කිරීමේ පියවර ගණන


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් ගූගල් HRT මයික්රොසොෆ්ට්
බිට් හැසිරවීම

ගැටළුව ශුන්‍ය ලීට්කෝඩ් විසඳුමට අංකයක් අඩු කිරීමේ පියවර ගණන සඳහන් කරයි නිඛිල. දී ඇති නිඛිලය 0 බවට පරිවර්තනය කිරීම සඳහා අවම පියවර ගණන සොයා ගන්න. ඔබට පියවර දෙකෙන් එකක් කළ හැකිය, එක්කෝ අඩු කරන්න හෝ නිඛිලය 1 න් බෙදන්න. ගැටළුව සරල බව පෙනේ, නමුත් විසඳුම හරහා යාමට පෙර, අපි උදාහරණ කිහිපයක් දකිමු .

අංකයක් ශුන්‍ය ලීට්කෝඩ් විසඳුම දක්වා අඩු කිරීමේ පියවර ගණන

n = 14
6

පැහැදිලි කිරීම: දී ඇති නිඛිලය (= 14) 0 දක්වා අඩු කිරීම සඳහා අවම පියවර ගණන පියවර 6 ක් අවශ්‍ය වේ. පළමුව, 14 න් 2 න් බෙදන්න. දැන් අපට ඉතිරිව ඇත්තේ 7 ක් පමණි. එවිට අපි 1 අඩු කරමු. දැන් අප සතුව ඇති සංඛ්‍යාව 6. අපි නැවත 2 න් බෙදන්නෙමු. ඉන්පසු අපි පූර්ණ සංඛ්‍යා (= 1) 3 දක්වා අඩු කිරීම සඳහා 0 තුන් වරක් අඩු කරමු.

8
4

පැහැදිලි කිරීම: 3 සිට 1 දක්වා අඩු කිරීම සඳහා අපි 8 බෙදීම් සහ 0 අඩු කිරීමේ මෙහෙයුමක් භාවිතා කරමු. පළමු පියවර 8 සිට 4 දක්වාත්, පසුව 4 සිට 2 දක්වාත්, 2 සිට 1 දක්වාත් අඩු කරයි. ඉන්පසු අපි 1 ලබා ගැනීම සඳහා 1 සිට 0 දක්වා අඩු කරමු.

අංකයක් ශුන්‍ය ලීට්කෝඩ් විසඳුම දක්වා අඩු කිරීම සඳහා පියවර ගණන සඳහා තිරිසන් බල ප්‍රවේශය

ගැටළුව සෑහෙන්න සම්මත වන අතර විවිධ පරීක්ෂණ වලදී කිහිප වතාවක්ම විමසා ඇත. කාල සීමාව යටතේ ගැටළුව විසඳීම සඳහා ගැටළුව සඳහා තිරිසන් බල විසඳුම ප්රමාණවත් නොවේ. තිරිසන් බල විසඳුම විසඳුම සඳහා පුනරාවර්තනය භාවිතා කරයි. එක් එක් නිඛිල සඳහා, අපට හැකි මෙහෙයුම් දෙකක් ඇති බැවින්. අපි ඒ දෙකම සිදු කර නැවත වෙනස් කරන ලද පූර්ණ සංඛ්‍යාවක් ඉල්ලා සිටිමු. විසඳුම සඳහා වන කාල සංකීර්ණතාව on ාතීය වන බැවින් විශාල යෙදවුම් සඳහා කාර්යක්ෂම නොවේ. කේත කරන විට විසඳුම ධාවන කාල දෝෂයක් බවට පත්වනු ඇත, මන්ද දශම කොටස අඩංගු සංඛ්‍යා කිසි විටෙකත් 0 දක්වා අඩු කිරීමට නොහැකි වනු ඇත.

සංඛ්‍යාවක් ශුන්‍ය ලීට්කෝඩ් විසඳුමකට අඩු කිරීම සඳහා පියවර ගණන සඳහා ප්‍රශස්ත ප්‍රවේශය

ගැටළුව සම්මත ගැටළු වලින් එකක් වන අතර එය ඉතා පුළුල් ලෙස දන්නා කරුණකි. අප 1 ක් අඩු කළහොත් ගැටළුව පහසුවෙන් විසඳා ගත හැක්කේ අපට අමුතු සංඛ්‍යාවක් හමු වූ විට පමණි. අපට ඉරට්ටේ සංඛ්‍යාවක් ලැබෙන විට එම සංඛ්‍යාව 2 න් බෙදන්න. මේ අනුව ගැටළුවේ විසඳුම පූර්ණ සංඛ්‍යාවේ සමානාත්මතාවය මත රඳා පවතී. අංකය ඉරට්ටේ වන විට අපි 2 සිට බෙදන්නේ ඇයි? 1 අඩු කිරීමට වඩා අඩක් කිරීමෙන් සංඛ්‍යාව අඩු කිරීම සැමවිටම වඩා හොඳ හෝ සමානව හොඳයි. එසේනම් අපි අමුතු සංඛ්‍යා බෙදන්නේ නැත්තේ ඇයි? මන්ද එවිට අපට දශම සංඛ්‍යා සංඛ්‍යාවක් තිබීම අවසන් වන අතර එය කිසිදු ආකාරයකින් මෙම මෙහෙයුම් දෙක භාවිතා කරමින් 0 දක්වා අඩු කළ නොහැක.

අංකයක් ශුන්‍ය ලීට්කෝඩ් විසඳුමට අඩු කිරීම සඳහා පියවර ගණන සඳහා ප්‍රශස්ත කේතය

සී ++ කේතය

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

int numberOfSteps (int num) {
    int cnt = 0;
    while(num){
        if(num&1)num--;
        else num/=2;
        cnt++;
    }
    return cnt;
}

int main(){
    cout<<numberOfSteps(14);
}
6

ජාවා කේතය

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

class Main
{
  public static int numberOfSteps (int num) {
        int cnt = 0;
        while(num > 0){
            if(num%2 == 1)num--;
            else num/=2;
            cnt++;
        }
        return cnt;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    System.out.print(numberOfSteps(14));
  }
}
6

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (ලොග්එන්), අපට ඉරට්ටේ සංඛ්‍යාවක් ලැබෙන සෑම විටම අපි පූර්ණ සංඛ්‍යාව 2 න් බෙදන්නෙමු. සෑම අමුතු සංඛ්‍යාවක්ම ඉන් 1 ක් අඩු කිරීමෙන් ඉරට්ටේ සංඛ්‍යාවක් බවට පරිවර්තනය වේ. මේ අනුව කාල සංකීර්ණතාව ල ar ු ගණකය බවට පත්වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1), අපි තනි විචල්‍යයක් භාවිතා කළ නිසා එය නියත අවකාශයකි. මේ අනුව අවකාශයේ සංකීර්ණතාව ද නියත ය.