پاسخ مسابقه تمرینی بیان – جمع زیردنباله ها

صورت سوال جمع زیر دنباله ها:

یک دنباله اعداد به شما داده می‌شود. فرض کنید به ازای هر زیر دنباله پیوسته از این دنباله ، مجموع اعداد زیر دنباله در یک لیست نگهداری شود. از شما خواسته شده است که تعداد اعداد متفاوت در این لیست را بدست آورید.

به عنوان مثال دنباله ‎ ‎ را در نظر بگیرید. این دنباله ‎ زیر دنباله متفاوت دارد: و و و و و که مجموع آنها به ترتیب ‎ و ‎و ‎و ‎و و ‎ می باشد. در نتیجه این لیست عنصر متفاوت دارد.

ورودی مساله:

در سطر اول فایل ورودی یک عدد ‎ ‎ قرار دارد که مشخص کننده ی تعداد تست ها می باشد. در هر کدام از ‎ ‎ تست بعدی یک دنباله شرح داده شده است، به این شکل که ابتدا یک عدد ‎ ‎ مشخص کننده ی تعداد اعضای دنباله و سپس ‎ عدد اعضای دنباله آمده اند‎.

تمام اعداد ورودی بین ‎ ‎ و ‎ قرار دارند.

خروجی مساله:

به ازای هر تست، پاسخ سوال را در یک خط جداگانه چاپ کنید.

ورودی و خروجی مثال:
مثال ورودی مثال خروجی
۲

۳

۳ ۲ ۱

۳

۱ ۱ ۱

۵

۳

 

پاسخ من به این سوال:

صورت سوال واضح است. من برای حل این مسئله از یک ماتریس بالامثلثی که به صورت  پویا ساخته میشود استفاده نمودم. اگر ابتدا مقادیر دنباله را در قطر اصلی ماتریس قرار دهیم با یکبار پیمایش و پرکردن تمام خانه های بالای قطر اصلی میتوانیم به تمام جمع های زیر دنباله ها برسیم. برای مثال ماتریس دنباله ی ‎   ابتدا به شکل زیر ساخته میشود:

۱  ۰  ۰
۰  ۲  ۰
۰  ۰  ۳

سپس مقادیر بالای قطر اصلی از جمع عناصر قطر اصلی به دست می آید. به این ترتیب که مقدار خانه (۱،۲) از جمع مقادیر (۱،۱) و (۲،۲) ، مقدار خانه (۲،۳) از جمع مقادیر (۲،۲) و (۳،۳) و بالاخره مقدار خانه (۱،۳) از جمع مقادیر خانه های (۱،۱) و (۲،۲) و (۳،۳) به دست می آید:

۱  ۳  ۶ 
۰  ۲  ۵
۰  ۰  ۳

برای دنباله های بزرگتر هم میتوان از این شیوه استفاده نمود. فقط باید دقت نمود که مقادیر تکراری از نتیجه محاسبات حذف شوند. به طور مثال در ماتریس بالا عنصر ۳ دوبار تکرار شده که تنها یکبار آن در محاسبات منظور میشود.

 

//======================================
// sum of subsequences by Mohsen Rashidi
//======================================

#include <iostream>
#include <fstream> 
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int main() {

	// باز کردن فایل ورودی
	ifstream inputFile( "problem3.in", ios::in );	

	// باز کردن فایل برای نمایش خروجی
	ofstream outputFile( "problem3Result.txt", ios::out );

	// تعداد دنباله های داده شده در فایل ورودی
	int numOfSequences;

	inputFile >> numOfSequences;
	cout << "\n" << "num of sequences: " << numOfSequences << endl;

	// اجرا به ازای تمام دنباله های ورودی
	for(int i = 1 ; i <= numOfSequences ; i++) {

		// بردار جمع زیردنباله ها
		vector <int> sumOfSubSequences;

		// تعداد عناصر دنباله ی جاری
		int numOfDigits;

		inputFile >> numOfDigits;

		cout << "\n\n" << "num of digits: " << numOfDigits;

		// تعریف و حافظه دهی ماتریس پویا با طول و عرضی
		// برابر با تعداد عناصر دنباله فعلی
		int** sequenceMatrix = new int*[numOfDigits];
		for( int b = 0 ; b < numOfDigits ; b++ )
			sequenceMatrix[b] = new int[numOfDigits];

		cout << "\n\n" << " digits: ";

		cout << "\n******************************************\n" ;

		// قرار دادن عناصر دنباله در قطر اصلی ماتریس برای انجام محاسبات و
		// همچنین گذاردن این مقادیر داخل بردار نگهدارنده جمع زیردنباله ها
		for( int a = 0 ; a < numOfDigits ; a++ ) {
			int digit;
			inputFile >> digit;
			cout << digit << " ";
			sequenceMatrix[a][a] = digit;
			sumOfSubSequences.push_back(digit);
		}

		cout << "\n******************************************";

		//getchar();

		// محاسبه جمع تمام زیردنباله ها و قراردادن این مقادیر 
		// در خانه های ماتریس بالا مثلثی و همچنین اضافه کردن این
		// مقادیر به بردار نگهدارنده جمع زیردنباله ها
		for( int d = 0 ; d < numOfDigits - 1 ; d++) {
			for( int e = d + 1 ; e < numOfDigits  ; e++) {
				sequenceMatrix[d][e] = 0;
				for( int f = d ; f <= e ; f++ ) {
					sequenceMatrix[d][e] += sequenceMatrix[f][f];
				}
				sumOfSubSequences.push_back(sequenceMatrix[d][e]);
			}
		}

		// مرتب کردن عناصر بردار برای حذف عناصر تکراری
		std::sort(sumOfSubSequences.begin(), sumOfSubSequences.end());

		// حذف عناصر تکراری از بردار
		vector <int>::iterator newLoc = std::unique(sumOfSubSequences.begin(), sumOfSubSequences.end()); 

		cout << "\nresult is: ";

		// نمایش پاسخ در کنسول و فایل خروج
		cout << newLoc -  sumOfSubSequences.begin() << "\n";
		outputFile << newLoc -  sumOfSubSequences.begin() << "\n";

		// بازپسدهی حافظه تخصیص داده شده به ماتریس پویا
		for( int l = 0 ; l < numOfDigits ; l++ )
			delete[] sequenceMatrix[l];
		delete[] sequenceMatrix;

	}
	return 0;
}

 

 

 

 

برنامه‌نویس ++‏C/C‏ - برنامه‌نویس سیستم‌های گرافیکی با استفاده از کتابخانه ‏OpenGL - برنامه‌نویس #‏C و ..‏

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

5 + 20 =

Back To Top