Algorithm Problems

Интересный сайт с алгоритмическими задачами. Поддерживаются C++, Java, Python.

Advertisements

CodeNirvana: Palidromic Numbers

Алгоритмами заниматься интересно. На сайте codenirvana.in опубликовано еще одно решение — проверка чисел на принадлежность к полиндромам:
Palindrome
Palindromic Number.

Т.е. проверка на принадлежность к числам, для которых исходные данные и результат этого алгоритма совпадают:
CodeNirvana: C Program To Reverse a Number.

Здесь обсуждается алгоритм поиска палидромов.

Java реализация
С++ реализация

Еще две реализации проверки на принадлежность к палидромным числам (С++).

А ниже реализации алгоритмов поиска палидромов в строках (С++).
Part 1
Part 2

Number Pattern #1

Решение простой алгоритмической задачи – генерация int последовательностей.

На сайте http://codenirvana.in есть такой challenge (easy level):

CHALLENGE DESCRIPTION:
Write a program that prints out the pattern generated according to the input (number) from the user.
Pattern input and output sample is given below, check the input and the following pattern generated for that condition (number). Make sure you program follow the same pattern logic for every input.

INPUT SAMPLE:
Your program should ask for a number F first and than print the pattern accordingly. E.g.

Enter a number: 4

OUTPUT SAMPLE:
For the input N=4 output will be
4444444
4333334
4322234
4321234
4322234
4333334
4444444

Ниже приводится мое решение (“С” for Windows). В коде два генератора последовательностей – итеративный и рекурсивный:

// lines_gen.cpp : Defines the entry point for the console application.
//

#include 
#include 
#include 

VOID init_line                          (PUINT	punLine, UINT unN);
VOID print_line                         (PUINT	punLine, UINT unN);
UINT proc_elem                          (PUINT	punLine, UINT unN, UINT unIdx);
UINT proc_array_rec                     (PUINT	punLine, UINT unN);
UINT proc_array_iter                    (PUINT	punLine, UINT unN);
UINT proc_array_iter_bak                (PUINT	punLine, UINT unN);

VOID init_line(PUINT	punLine, UINT unN)
{
	UINT unIdx;
	for(unIdx = 0; unIdx = punLine[unIdx+1])
		unRes = proc_elem(punLine, unN, unIdx+1);
	else
		unRes = punLine[unIdx+1];

	if(unRes)
	{
		punLine[unIdx] = unRes;
		return punLine[unIdx];
	}
	else
		return 0;
}

UINT proc_array_rec(PUINT	punLine, UINT unN)
{
	UINT unCount = 0;

	print_line(punLine, unN);
	while(TRUE)
	{
		unCount++;
		if(!proc_elem	(punLine, unN, 0))
			break;
		print_line(punLine, unN);
	}

	return unCount;
}

UINT proc_array_iter(PUINT punLine, UINT unN)
{
	UINT unIdx;
	UINT unIdxIn;

	print_line(punLine, unN);
	for(unIdx = 1; unIdx < unN; unIdx++)
	{
		for(unIdxIn = 0; unIdxIn <= unIdx; unIdxIn++)
			punLine[unIdxIn] = unIdx+1;
		print_line(punLine, unN);
	}
	return unIdx;
}

UINT proc_array_iter_bak(PUINT punLine, UINT unN)
{
	UINT unIdx;
	UINT unIdxIn;

	print_line(punLine, unN);
	for(unIdx = 1; unIdx < unN; unIdx++)
	{
		UINT unBackIdx = unN-unIdx;
		for(unIdxIn = 0; unIdxIn <= (unBackIdx-1); unIdxIn++)
			punLine[unIdxIn] = unBackIdx;
		print_line(punLine, unN);
	}
	return unIdx;
}

INT _tmain(int argc, _TCHAR* argv[])
{
	UINT	unN		= 0;
	PUINT	punLine	= NULL;
	UINT	unCount;

	_tprintf(_T("Enter a number : "));
	_tscanf_s(_T("%d"), &unN);

	if(!unN)
		return 0;

	punLine = (PUINT) malloc(unN*sizeof(UINT));

	init_line(punLine, unN);
	unCount = proc_array_iter(punLine, unN);
	_tprintf(_T("Total count = %d\n"), unCount);
	_tprintf(_T("-----------------\n"));
	unCount = proc_array_iter_bak(punLine, unN);
	_tprintf(_T("Total count = %d\n"), unCount);
	_tprintf(_T("-----------------\n"));
	unCount = proc_array_rec(punLine, unN);
	_tprintf(_T("Total count = %d\n"), unCount);

	free(punLine);

	return 0;
}

Output:

Enter a number : 5
line = 1 2 3 4 5
line = 2 2 3 4 5
line = 3 3 3 4 5
line = 4 4 4 4 5
line = 5 5 5 5 5
Total count = 5
—————–
line = 5 5 5 5 5
line = 4 4 4 4 5
line = 3 3 3 4 5
line = 2 2 3 4 5
line = 1 2 3 4 5
Total count = 5
—————–
line = 1 2 3 4 5
line = 2 2 3 4 5
line = 3 3 3 4 5
line = 4 4 4 4 5
line = 5 5 5 5 5
Total count = 5

lines_gen.c
output.txt

Java:

/**
 *
 */
package com.smansoft;

/**
 * @author SMan
 *
 */
public class LinesGen {

	/**
	 *
	 */
	int line[] = null;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int inNum = Integer.parseInt(args[0]);		

		System.out.printf("Number = %d\n", inNum);

		LinesGen linesGen = new LinesGen(inNum);
		linesGen.initLine();

		int count = linesGen.procArrayIter();
		System.out.printf("Total count = %d\n", count);
		count = linesGen.procArrayIterBak();
		System.out.printf("Total count = %d\n", count);
		count = linesGen.procArrayRec();
		System.out.printf("Total count = %d\n", count);
	}

	/**
	 *
	 * @param size
	 */
	public LinesGen(int size) {
		line = new int[size];
	}

	/**
	 *
	 */
	public void initLine() {
		for (int idx = 0; idx < line.length; idx++) {
			line[idx] = (idx + 1);
		}
	}

	/**
	 *
	 */
	public void printLine() {
		System.out.print("line = ");
		for (int idx = 0; idx < line.length; idx++) {
			System.out.printf("%d ", line[idx]);
		}
		System.out.println("");
	}

	/**
	 *
	 * @return
	 */
	public int procArrayRec() {
		int count = 0;
		printLine();
		while (true) {
			count++;
			if (procElem(0) == 0)
				break;
			printLine();
		}
		return count;
	}

	/**
	 *
	 * @return
	 */
	public int procArrayIter() {
		int idx;
		printLine();
		for (idx = 1; idx < line.length; idx++) {
			for (int idxIn = 0; idxIn <= idx; idxIn++) {
				line[idxIn] = idx + 1;
			}
			printLine();
		}
		return idx;
	}

	/**
	 *
	 * @return
	 */
	public int procArrayIterBak() {
		int idx;
		printLine();
		for (idx = 1; idx = line[idx + 1])
			res = procElem(idx + 1);
		else
			res = line[idx + 1];

		if (res > 0) {
			line[idx] = res;
			return line[idx];
		} else
			return 0;
	}
}

Output (ant run.LinesGen):

run.LinesGen:
     [java] Number = 5
     [java] line = 1 2 3 4 5
     [java] line = 2 2 3 4 5
     [java] line = 3 3 3 4 5
     [java] line = 4 4 4 4 5
     [java] line = 5 5 5 5 5
     [java] Total count = 5
     [java] line = 5 5 5 5 5
     [java] line = 4 4 4 4 5
     [java] line = 3 3 3 4 5
     [java] line = 2 2 3 4 5
     [java] line = 1 2 3 4 5
     [java] Total count = 5
     [java] line = 1 2 3 4 5
     [java] line = 2 2 3 4 5
     [java] line = 3 3 3 4 5
     [java] line = 4 4 4 4 5
     [java] line = 5 5 5 5 5
     [java] Total count = 5

LinesGen.java
LinesGen.zip (including ant script)
joutput.txt

Еще одно решение (“С” for Windows) – компактное и эффективное с генерацией конечной последовательности (любезно предложено подписчиками codenirvana.in):

// lines_gen_short.cpp : Defines the entry point for the console application.
//

#include 
#include 

void seq_generator(int nN)
{
	int i,j;
	for(i=nN;i>=1;i--)
	{
		for(j=nN;j>=i;j--)
			_tprintf(_T("%d"),j);
		for(j=1;j<(i*2)-1;j++)
			_tprintf(_T("%d"),i);
		for(j=i+1;j<=nN;j++)
			_tprintf(_T("%d"),j);
		_tprintf(_T("\n"));
	}
	for(i=2;i=i;j--)
			_tprintf(_T("%d"),j);
		for(j=1;j<(i*2)-1;j++)
			_tprintf(_T("%d"),i);
		for(j=i+1;j<=nN;j++)
			_tprintf(_T("%d"),j);
		_tprintf(_T("\n"));
	}
	return;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int nN;

	_tprintf(_T("Enter a number : "));
	_tscanf_s(_T("%d"), &nN);

	if(!nN)
		return 0;

	seq_generator(nN);

	return 0;
}

Output:

Enter a number : 4
4444444
4333334
4322234
4321234
4322234
4333334
4444444

lines_gen_short.c
output_short.txt

SManSoft Ltd.

SManSoft Ltd.

This blog is a mirror of the site SManSoft Ltd. blog, that has been created and supported by Sergey Manoylo to document software development activity in Software Development (C/C++, Java, Windows, Linux, Android, Kernel Level).

Blog Mirrors:

mirror: http://blog.smansoft.com
mirror: https://smansoft.wordpress.com

Contact info:

Sergey Manoylo

mobile phone: +380-67-150-2244
e-mail: sman(at)smansoft.com
e-mail: blog(at)smansoft.com
e-mail: smansoft(at)ukr.net
Skype ID: smansoft.net
Telegram: https://t.me/smansoft
GitHub: https://github.com/smansoft

Kharkov, Ukraine