کوچنی ښه اساس


مشکل کچه سخت
په مکرر ډول دننه پوښتل کیږي د ګوګل
دوه لمبري پلټنه ریاضی تار

ستونزه بیان

فرض کړئ چې موږ د ټولو ارزښتونو لپاره n یو بشپړ n درکړی دی n بیس k 1 دي کله چې ښه بیس k> = 2. فرض کړئ چې موږ یو ورکړی تار د - ب .ه شمیره 'n'. د ستونزې بیان د N کوچنۍ کوچنۍ ښه اډه موندلو او بیرته راستنیدو غوښتنه کوي تار بڼه

بېلګه

کوچنی ښه اساس

String n = “15”
2

تشریح: 15 کله چې په 2 بیس کې لیکل شوی نو 1111 دی.

String n = “20”
19

تشریح: 20 کله چې په 19 بیس کې لیکل شوی نو 11 دی.

د کوچني ښه اساس اساس ستونزې لپاره الګوریتم

1. Set y to n-1.
2. Add the n-1 into the List.
3. From the i=2 to i< 63,
  1. Find out the val = pow of (y, 1.0 / i).
  2. From j=0 to j > - 3 and val + j > 1.
    1. Set d = val + j.
    2. And check if n % d is equal to 0.
      1. Find out this polynomial 1 + d + d ^ 2 + d ^ 3 + ... + d ^ i for d and up the current value of I and store into the sum.
    3. Check if this polynomial’s sum is equal to the n.
      1. Then add the value of d to the list.
4. Repeat the third process until the loop finishes.
5. Get the last element of the list and return that value.

تشریح

په شمیره کې n ورکړل شو تار ب .ه. هره شمیره n د اساس اعظمي ارزښت لري کوم چې دی n1. لدې چې ارزښت کولی شي له 3 څخه تر 10 change 18 پورې بدل شي ، کوم چې په اعظمي 64 ګsو کې ځای کیدی شي. ترټولو کوچنۍ اډه 2 کیدی شي او 63 ته به لاړ شي. اعظمي اساس چې موږ یې محاسبه کولی شو د n-1 دی ، د n ارزښت لپاره ، او لږترلږه 2 دی.

موږ اړتیا لرو چې اساس یې راټیټ کړو ترڅو د هر یو ترټولو خورا خورا اوږده اوږدوالي انځور ومومئ. د هر یو لپاره. د ګsو شمیره ، موږ به هڅه وکړو چې دا وموم چې ایا دلته یو اساس شتون لري چې درناوی ورته برابر کړي. ورکړل شوي ارزښت = م ، دا ستونزه د d او n بشپړ نمبرونو موندلو لپاره چې پوره کوي ،

m = 1 + d + d ^ 2 + d ^ 3 +… + d ^ i.

د 'i' سره هغه ارزښت دی چې هرځل بدل کیدی شي هرکله چې موږ د صف څخه تیر شو (د دې هدف سره چې b به لږترلږه شي).

د معادلې سره سم ، موږ تل د یو جوړه په توګه ځواب لرو په ورته ډول D1 = m-1. نو موږ به د ځواب احتمالي ارزښتونه لنډ کړو چې موږ یې په لیست کې داخل کړل. ارزښتونه (d1 ،… ، dn) په لیست کې دي او موږ به وروستی ارزښت لاسته راوړو. موږ اړتیا لرو چې د 1 + b + b b 2 + b ^ 3 +… + b ^ اډیټ پولیټیکل معلوم کړو.

موږ به په یوه فنکشن تعقیب کړو ، له هغه ځایه چې موږ د هرې ممکنه شمیرې موندلو لپاره ځو. هغه لوپ چې موږ اخیستی د 62 پورې دی ځکه چې شمیره تر 64 ډیجیټونو پورې رامینځته کیدی شي ، مګر د 63 ممکنه اخیستل به د ډیر جریان لامل شي. موږ به دې کار ته دوام ورکړو تر هغه چې موږ لږترلږه ارزښت ونه مومو او په ورته وخت کې موږ به دا لیست کې اضافه کړو. نو موږ یوازې دې ته اړتیا لرو چې ترټولو کوچنۍ اډه ومومئ او وروستی مو ترلاسه کړئ.

کوډ

د کوچني ښه اساس موندلو لپاره C ++ کوډ

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

long getGetPolynomial(long, int);
string getMinGoodBase(string n)
{
    long x = stoi(n);
    vector<long> listt;
    listt.push_back(x-1);
    long y = x-1;
    for (int i = 2; i < 63; i++)
    {
        double val = pow(y, 1.0 / i);
        long value = (long) val;
        for (int j = 0; j > -3 && value + j > 1; j--)
        {
            long d = value + j;
            if (y % d == 0)
            {
                long poly = getGetPolynomial(d, i);

                if (poly == x)
                {
                    listt.push_back(d);
                }
            }
        }
    }
    long end = listt[listt.size() - 1];
    string out = to_string(end);
    return out;
}
long getGetPolynomial(long d, int n)
{
    long out = 1;
    long k = 1;
    for (int i = 0; i < n; i++)
    {
        k *= d;
        out += k;
    }
    return out;
}
int main()
{
    string num="15";
    cout<<getMinGoodBase(num);
}
2

د کوچني ښه اساس موندلو لپاره جاوا کوډ

import java.util.ArrayList;
import java.util.List;

class GoodBase
{
    public static String getMinGoodBase(String n)
    {
        long x = Long.parseLong(n);
        List<Long> listt = new ArrayList<>();
        listt.add(x-1);
        long y = x-1;
        for (int i = 2; i < 63; i++)
        {
            double val = Math.pow(y, 1.0 / i);
            long value = (long) val;
            for (int j = 0; j > -3 && value + j > 1; j--)
            {
                long d = value + j;
                if (y % d == 0)
                {
                    long poly = getPolynomial(d, i);

                    if (poly == x)
                    {
                        listt.add(d);
                    }
                }
            }
        }
        long end = listt.get(listt.size() - 1);
        return end+"";
    }
    public static long getPolynomial(long d, int n)
    {
        long out = 1;
        long k = 1;
        for (int i = 0; i < n; i++)
        {
            k *= d;
            out += k;
        }
        return out;
    }
    public static void main(String args[])
    {
        String num="15";
        System.out.println(getMinGoodBase(num));
    }
}
2

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n)2هلته "n" د تار تار اوږدوالی دی.

د ځای پیچلتیا

اې (N) هلته "n" د تار تار اوږدوالی دی.