จำนวนอาร์เรย์ที่องค์ประกอบที่อยู่ติดกันทั้งหมดโดยที่หนึ่งในนั้นแบ่งอีกองค์ประกอบหนึ่งใน C++

กำหนดจำนวนเต็มสองจำนวนชื่อ 'หนึ่ง' และ 'อีกจำนวนหนึ่ง' เป้าหมายคือการหาจำนวนอาร์เรย์ที่เป็นไปได้ −

• องค์ประกอบในอาร์เรย์อยู่ในช่วงระหว่าง 1 ถึง "อื่น"

• องค์ประกอบทั้งหมดของอาร์เรย์เป็นแบบที่ arr[i] แบ่ง arr[i+1] หรือ arr[i+1] แบ่ง arr[i+2]....และอื่นๆ

• ความยาวของอาร์เรย์คือ "หนึ่ง"

ตัวอย่าง

อินพุต

one = 3, another = 2

ผลลัพธ์

Count of arrays in which all adjacent elements are such that one of them divide the another are: 8

คำอธิบาย

The arrays will be:
[ 1,1,1 ], [ 1,1,2 ], [ 1,2,1 ], [ 1,2,2 ], [ 2,1,1 ], [ 2,1,2 ], [ 2,2,1 ], [ 2,2,2 ]

อินพุต

one = 2, another = 3

ผลลัพธ์

Count of arrays in which all adjacent elements are such that one of them divide the another are: 7

คำอธิบาย

The arrays will be:
[ 1,1 ], [ 2,2 ], [ 3,3 ], [ 1,2 ], [ 1,3 ], [ 2,2 ], [ 3,3 ]

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

เรารู้ว่าองค์ประกอบแรกของแต่ละอาร์เรย์สามารถเป็นตัวเลขใดก็ได้ในช่วง[1,another] องค์ประกอบถัดไปจะเป็นผลคูณของค่าก่อนหน้าหรือตัวประกอบของค่าก่อนหน้าเสมอเพื่อให้มีเงื่อนไขการหาร นอกจากนี้ ตัวประกอบหรือตัวคูณควรน้อยกว่า 'อีกตัวหนึ่ง' เราจะใช้การเขียนโปรแกรมแบบไดนามิกเพื่อจัดเก็บการคำนวณ สำหรับสิ่งนี้เราใช้ array arr[][].arr[1][another] จะเป็น 1 เนื่องจากเป็นอาร์เรย์องค์ประกอบเดียว arr[i][j]=arr[i-1][j]+factors of Previous element+multiples of Previous element (น้อยกว่าอื่น )

• นำจำนวนเต็มมารวมกันเป็นอินพุต

• ฟังก์ชัน subjected_elements(int first, int second) คืนค่าจำนวนอาร์เรย์ที่องค์ประกอบที่อยู่ติดกันทั้งหมดเป็นแบบที่หนึ่งในนั้นแบ่งอีกส่วน

• นับเริ่มต้นเป็น 0 และอาร์เรย์ arr[size][size].

• เริ่มต้นทั้งหมดนับเป็น 0 โดยใช้ memset

• ใช้เวกเตอร์สองตัว − vec สำหรับเก็บปัจจัยและ vec_2 สำหรับเก็บทวีคูณ

• สำรวจโดยใช้สองลูปจาก i=t ถึง i=second และ j=2*i ถึง j=second เพิ่ม j โดย i.

• เพิ่ม i ไปที่ vec[j] และ j ไปที่ vec_2[i] หลังจาก j loop ก็เพิ่ม i ไปที่ vec[i].

• ตั้งค่า arr[1][i] ใช้สำหรับวนซ้ำ

• Traverse array อีกครั้ง และตอนนี้ traverse vec และ vec_2 และเพิ่มปัจจัยและตัวคูณให้กับ arr[i][j].

• ในตอนท้ายให้เพิ่ม arr[first][i] ทั้งหมดเพื่อนับและล้าง vec[i] และ vec_2[i].

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
#define size 1000
int adjacent_elements(int first, int second){
   int count = 0;
   int arr[size][size];
   memset(arr, 0, sizeof arr);
   vector<int> vec[size], vec_2[size];
   memset(vec, 0, sizeof vec);
   memset(vec_2, 0, sizeof vec_2);
   for (int i = 1; i <= second; i++){
      for (int j = 2*i; j <= second; j += i){
         vec[j].push_back(i);
         vec_2[i].push_back(j);
      }
      vec[i].push_back(i);
   }
   for (int i = 1; i <= second; i++){
      arr[1][i] = 1;
   }
   for (int i = 2; i <= first; i++){
      for (int j = 1; j <= second; j++){
         arr[i][j] = 0;
         for (auto it: vec[j]){
            arr[i][j] += arr[i−1][it];
         }
         for (auto it : vec_2[j]){
            arr[i][j] += arr[i−1][it];
         }
      }
   }
   for (int i = 1; i <= second; i++){
      count = count + arr[first][i];
      vec[i].clear();
      vec_2[i].clear();
   }
   return count;
}
int main(){
   int one = 2, another = 2;
   cout<<"Count of arrays in which all adjacent elements are such that one of them divide the another are: "<<adjacent_elements(one, another);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of arrays in which all adjacent elements are such that one of them divide the another are: 4